Functions & Recursion

In a nutshell

A C function has a return type, a name, a parameter list, and a body. In Java you wrote methods that lived inside a class; in C, functions live at file scope and there is no class holding them together. Every argument is copied (pass-by-value), just like a Java primitive. Every function call allocates a stack frame for its parameters and locals, so recursion is literally a stack of frames.

Practice this topic: C Functions drill, or browse the practice gallery.

After this lesson, you will be able to:

• Write function prototypes and definitions and say what each contributes
• Explain pass-by-value and its implications for modifying a caller’s variable
• Identify where a variable is in scope and why globals are usually the wrong answer
• Write a recursive function with a correct base case and predict how the call stack grows
• Say when recursion is the right choice and when a loop is clearer

Quick reference

Coming from CSCD 210

You wrote methods, you called them, you knew about local versus instance scope, and you probably wrote at least one recursive method. Three differences in C. Functions live at file scope; there are no classes. C is strictly pass-by-value, so a function cannot directly modify a caller’s int (pointers in week 6 solve this). And you must write a prototype before calling a function whose definition appears later in the file.

Defining and calling

Structure

#include <stdio.h>

/* prototype: declares the function before main */
int add(int a, int b);

int main(void)
{
    int result;
    result = add(3, 4);
    printf("%d\n", result);     /* 7 */
    return 0;
}

/* definition: implements the function */
int add(int a, int b)
{
    return a + b;
}

The prototype tells the compiler the function exists, its return type, and its parameter types. Without it, calling add before its definition causes an implicit-declaration warning under -Wall and can silently pick the wrong return type. Always declare before main, define after.

Pass-by-value

Every argument is copied. Modifying the copy does not affect the caller.

void try_to_change(int x)
{
    x = 99;
    printf("Inside: %d\n", x);    /* 99 */
}

int main(void)
{
    int num = 5;
    try_to_change(num);
    printf("Outside: %d\n", num); /* 5, unchanged */
    return 0;
}

Java was the same for primitives. The difference: Java let you pass an object reference and modify the object’s fields. C has no objects. To modify a caller’s variable, you either return a new value and let the caller assign it, or (in week 6) pass a pointer.

int doubled(int x)
{
    return x * 2;
}

int main(void)
{
    int val = 5;
    val = doubled(val);      /* caller updates its own variable */
    printf("%d\n", val);     /* 10 */
    return 0;
}

Check your understanding (predict the output)

#include <stdio.h>

void double_it(int x)
{
    x = x * 2;
}

int main(void)
{
    int val = 5;
    double_it(val);
    printf("%d\n", val);
    return 0;
}

Scope

Variables declared inside a function (or block) are local to that block. They come into existence when the block starts and vanish when it ends.

int main(void)
{
    int x = 10;

    if (x > 5) {
        int y = 20;            /* y exists only inside this if block */
        printf("%d\n", y);
    }
    /* printf("%d\n", y); would fail: y is out of scope */

    return 0;
}

Global variables (declared outside any function) are visible everywhere in the file. Avoid them when you can. They make code harder to test and invite bugs in multi-threaded code. Pass values through parameters instead.

int count = 0;                 /* global; avoid when possible */

void increment(void)
{
    count++;                   /* silently modifies shared state */
}

When a global is genuinely the right tool (a configuration constant, a real singleton), keep it obviously named (g_config, or all-caps for const) so every use is visible.

Recursion

A recursive function calls itself. Every recursive function needs a base case (when to stop) and a recursive case (when to call itself with a smaller input).

int factorial(int n)
{
    if (n <= 1) {                       /* base case */
        return 1;
    }
    return n * factorial(n - 1);        /* recursive case */
}

Each call gets its own stack frame. Recursive calls stack up literally:

factorial(4) waits for factorial(3)
  factorial(3) waits for factorial(2)
    factorial(2) waits for factorial(1)
      factorial(1) returns 1
    factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Without a base case (or with one never reached), the stack grows until it hits the OS stack limit (typically a few MB). The program dies with a stack overflow (signal SIGSEGV). For the full picture of what a stack frame contains and how the OS allocates it, see the machine-model deep-dive.

Not every problem wants recursion. The classic fib definition is mathematically clean and operationally awful:

int fib(int n)
{
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

Each call makes two more. fib(30) does about a million duplicated calls. A plain for loop computes the same sequence in 30 steps. Recursion is a tool; reach for a loop when a loop is clearer.

Check your understanding (what is missing?)

int sum(int n)
{
    return n + sum(n - 1);
}

A classmate calls sum(4) expecting 10. The program crashes with a segmentation fault instead. What is missing, and what is the mechanism behind the crash?

int sum(int n)
{
    if (n <= 0) {
        return 0;
    }
    return n + sum(n - 1);
}

What comes next

Next, Arrays & Strings shows how C stores sequences and why a string is just a char array with a null terminator. Drill this page: C Functions or the practice gallery.