Advanced Functions

Recursion is like two mirrors facing each other -- images nest within themselves until the distant point of light vanishes. A function that calls itself solves problems through this power of progressive reduction.

Recursion Principles

Recursion is a programming technique where a function calls itself directly or indirectly. Every recursion must have two elements:

1. Recursive condition: the problem can be broken down into smaller subproblems of the same kind
2. Base case (terminating condition): the smallest subproblem has a direct answer and no longer recurses

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

Take factorial(4) as an example, the execution process:

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24

Classic Recursion Examples

Factorial

The definition of n factorial: n! = n x (n-1)!, and 0! = 1.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Note that the long type has a limited range; factorial(20) is already close to the 64-bit limit.

Fibonacci Sequence

Fibonacci definition: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).

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

Tower of Hanoi

Move n disks from peg A to peg C, using peg B as auxiliary. Rule: a larger disk cannot be placed on a smaller one.

#include <stdio.h>

void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        printf("%c -> %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, to, mid);
    printf("%c -> %c\n", from, to);
    hanoi(n - 1, mid, from, to);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

The idea: first move the top n-1 disks to the auxiliary peg, move the largest disk to the target peg, then move the n-1 disks from the auxiliary peg to the target peg. 3 disks require 7 moves; n disks require 2^n - 1 moves.

Example

Recursively compute the sum of an integer's digits:

#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(12345));
    printf("%d\n", digit_sum(7));
    return 0;
}

15
7

digit_sum(12345) = 5 + digit_sum(1234) = 5 + 4 + digit_sum(123) = ... = 5+4+3+2+1 = 15.

Variable Scope

Scope determines which regions of code can see and use a variable.

Block Scope

Variables defined within {} are only visible inside that block and are destroyed when the block ends:

int main(void) {
    int x = 10;
    {
        int y = 20;
        printf("%d %d\n", x, y);
    }
    printf("%d\n", x);
    return 0;
}

y exists only in the inner block and cannot be accessed from the outer block.

File Scope

Variables defined outside all functions have file scope and are visible from their definition to the end of the file. These are called global variables:

int count = 0;

void increment(void) {
    count++;
}

int main(void) {
    increment();
    increment();
    printf("%d\n", count);
    return 0;
}

Name Shadowing

A variable in an inner scope shadows a variable with the same name in an outer scope:

int x = 100;

int main(void) {
    int x = 10;
    printf("%d\n", x);
    return 0;
}

The output is 10; the inner x shadows the global x. The global x cannot be directly accessed inside the inner block.

Storage Classes

Storage classes determine a variable's lifetime and visibility. C has four storage class keywords: auto, static, extern, and register.

auto

auto is the default storage class for local variables and is usually omitted. Variables are created when the block is entered and destroyed when the block is exited:

void func(void) {
    auto int x = 10;
}

This is equivalent to int x = 10;.

static

When static modifies a local variable, the variable exists for the entire program runtime, but its scope remains limited to the function. Key property: it is initialized only once, and subsequent calls retain the previous value.

#include <stdio.h>

void counter(void) {
    static int count = 0;
    count++;
    printf("Call #%d\n", count);
}

int main(void) {
    counter();
    counter();
    counter();
    return 0;
}

Call #1
Call #2
Call #3

Without static, count would be reinitialized to 0 each time, always printing "Call #1".

When static modifies a global variable or function, it restricts its visibility to the current file (internal linkage); other source files cannot access it via extern.

extern

extern declares a global variable defined in another source file, telling the compiler "this variable exists, but is not defined in the current file":

file1.c:

int shared_data = 42;

file2.c:

#include <stdio.h>

extern int shared_data;

int main(void) {
    printf("%d\n", shared_data);
    return 0;
}

extern does not allocate memory; it is only a declaration. Multi-file projects need extern to share global data.

register

register suggests the compiler store the variable in a CPU register for faster access:

void fast_loop(void) {
    register int i;
    for (i = 0; i < 1000000; i++) {
    }
}

Modern compilers are very good at optimization and typically place frequently used variables in registers automatically, so the register hint has little effect. Note: you cannot take the address of a register variable (&), because registers do not have memory addresses.

Example

Iterative Fibonacci using a loop (avoiding recursion's repeated computation):

#include <stdio.h>

long fib_iter(int n) {
    if (n <= 2) return 1;
    long prev = 1;
    long curr = 1;
    long next;
    int i;

    for (i = 3; i <= n; i++) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    int i;
    for (i = 1; i <= 10; i++) {
        printf("F(%d) = %ld\n", i, fib_iter(i));
    }
    return 0;
}

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

This iterative version has O(n) time complexity, far better than the naive recursion's O(2^n).

❓ FAQ

📖 Summary

• Recursion must include a base case, or the stack will overflow
• Naive recursive Fibonacci is inefficient; real problems need loops or memoization
• Local variables have block scope; global variables have file scope
• static local variables persist throughout the program, but their scope remains unchanged
• extern enables cross-file variable sharing; register has little significance in modern compilers

📝 Exercises

1. Write a recursive function void print_reverse(int n) that prints the digits of a positive integer in reverse order (e.g., 123 outputs 3 2 1).
2. Write a function that uses a static variable to count how many times it has been called. Call it 5 times in main, then print the count.
3. Implement binary search recursively: search for a target value in a sorted array; return the index if found, or -1 if not found.