Functions

Recursion

Master recursive functions - functions that call themselves. Learn base cases, recursive cases, stack behavior, classic recursion problems, and when recursion vs iteration is appropriate.

Understanding Recursion

Recursion is when a function calls itself to solve a problem. It's a powerful technique for problems that can be broken into smaller, similar subproblems. Each recursive call works on a smaller piece of the problem until reaching a base case - the simplest version that can be solved directly without further recursion. Understanding recursion requires thinking differently about problem-solving.

Every recursive function must have two components: a base case (stopping condition) and a recursive case (calling itself with a smaller problem). Without a base case, recursion continues infinitely, causing stack overflow. The recursive case must make progress toward the base case, ensuring the function eventually terminates.

C
#include <stdio.h>

/* Simple recursive countdown */
void countdown(int n) {
    /* Base case: Stop when n reaches 0 */
    if (n == 0) {
        printf("Liftoff!\n");
        return;
    }
    
    /* Recursive case: Print and call with smaller n */
    printf("%d...\n", n);
    countdown(n - 1);  // Recursive call
}

int main(void) {
    countdown(5);
    return 0;
}

/* Output:
5...
4...
3...
2...
1...
Liftoff!
*/

Recursion Requirements:

Base Case: Condition to stop recursion
Recursive Case: Function calls itself
Progress: Each call moves toward base case
Return: Results combine to solve original problem

Classic Recursive Problems

Factorial

Factorial (n!) is the product of all positive integers up to n. It's defined recursively: n! = n Ã— (n-1)!, with base case 0! = 1. This classic example demonstrates how recursive definitions translate directly to code.

C
/* Recursive factorial */
int factorial(int n) {
    /* Base case */
    if (n <= 1) {
        return 1;
    }
    
    /* Recursive case: n! = n Ã— (n-1)! */
    return n * factorial(n - 1);
}

/* How it works: factorial(5)
   factorial(5) = 5 * factorial(4)
                = 5 * (4 * factorial(3))
                = 5 * (4 * (3 * factorial(2)))
                = 5 * (4 * (3 * (2 * factorial(1))))
                = 5 * (4 * (3 * (2 * 1)))
                = 5 * (4 * (3 * 2))
                = 5 * (4 * 6)
                = 5 * 24
                = 120
*/

int main(void) {
    printf("5! = %d\n", factorial(5));  // 120
    printf("10! = %d\n", factorial(10));  // 3628800
    return 0;
}

/* Iterative equivalent (for comparison) */
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Fibonacci Sequence

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13...) where each number is the sum of the previous two. Fibonacci demonstrates recursion elegantly but has performance issues - the naive recursive version recalculates the same values repeatedly.

C
/* Naive recursive Fibonacci (inefficient) */
int fibonacci(int n) {
    /* Base cases */
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    /* Recursive case: fib(n) = fib(n-1) + fib(n-2) */
    return fibonacci(n - 1) + fibonacci(n - 2);
}

/* Problem: Exponential time complexity
   fibonacci(5) calls fibonacci(4) and fibonacci(3)
   fibonacci(4) calls fibonacci(3) and fibonacci(2)
   fibonacci(3) is calculated TWICE!
   Gets worse as n increases
*/

int main(void) {
    for (int i = 0; i < 10; i++) {
        printf("fib(%d) = %d\n", i, fibonacci(i));
    }
    return 0;
}

/* Better: Iterative version (much faster) */
int fibonacci_iterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int prev2 = 0, prev1 = 1;
    int current;
    
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return current;
}

/* Memoization: Cache results to avoid recalculation */
int fib_memo[100];  // Cache array

int fibonacci_memoized(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    /* Check cache */
    if (fib_memo[n] != 0) {
        return fib_memo[n];
    }
    
    /* Calculate and cache */
    fib_memo[n] = fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2);
    return fib_memo[n];
}

Sum of Array Elements

Recursion can process arrays by handling one element and recursively processing the rest. This demonstrates how recursion reduces problem size with each call.

C
/* Recursive array sum */
int sum_array(int arr[], int size) {
    /* Base case: empty array */
    if (size == 0) {
        return 0;
    }
    
    /* Recursive case: first element + sum of rest */
    return arr[0] + sum_array(arr + 1, size - 1);
}

/* How it works: sum_array([1,2,3,4,5], 5)
   = 1 + sum_array([2,3,4,5], 4)
   = 1 + (2 + sum_array([3,4,5], 3))
   = 1 + (2 + (3 + sum_array([4,5], 2)))
   = 1 + (2 + (3 + (4 + sum_array([5], 1))))
   = 1 + (2 + (3 + (4 + (5 + sum_array([], 0)))))
   = 1 + (2 + (3 + (4 + (5 + 0))))
   = 15
*/

int main(void) {
    int numbers[] = {1, 2, 3, 4, 5};
    int total = sum_array(numbers, 5);
    printf("Sum: %d\n", total);  // 15
    return 0;
}

The Call Stack

Recursive calls use the call stack - a memory region storing function call information. Each recursive call pushes a new frame onto the stack with local variables and return address. When a function returns, its frame is popped. Deep recursion can exhaust stack space, causing stack overflow. Understanding the stack helps you reason about recursion and its memory usage.

C
/* Stack visualization for factorial(3) */

// Call: factorial(3)
// Stack Frame 3: n=3, waiting for factorial(2)
//   |
//   v Call: factorial(2)
//   Stack Frame 2: n=2, waiting for factorial(1)
//     |
//     v Call: factorial(1)
//     Stack Frame 1: n=1, returns 1
//     Stack Frame 2: returns 2 * 1 = 2
//   Stack Frame 3: returns 3 * 2 = 6
// Final result: 6

/* Stack overflow example (dangerous!) */
void infinite_recursion(int n) {
    printf("%d\n", n);
    infinite_recursion(n + 1);  // Never stops!
}
// Eventually: "Segmentation fault" or "Stack overflow"

/* Deep recursion example */
int deep(int n) {
    if (n == 0) return 0;
    return 1 + deep(n - 1);
}

int main(void) {
    // deep(10) - 10 stack frames - OK
    // deep(100000) - 100000 frames - May crash!
    printf("%d\n", deep(10));
    
    // This might crash:
    // printf("%d\n", deep(1000000));
    
    return 0;
}

/* Tail recursion optimization */
// Some compilers optimize tail recursion (last operation is recursive call)
int factorial_tail(int n, int accumulator) {
    if (n <= 1) {
        return accumulator;
    }
    return factorial_tail(n - 1, n * accumulator);
}

int factorial_tail_wrapper(int n) {
    return factorial_tail(n, 1);
}
// Compiler can optimize to iteration (no stack buildup)

Advanced Recursive Patterns

Tree Traversal

Recursion naturally handles tree structures. Each node processes its value and recursively processes its children. This pattern appears in file systems, expression trees, and many data structures.

C
/* Binary tree node */
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

/* Recursive tree traversal */
void inorder_traversal(Node *root) {
    if (root == NULL) {
        return;  // Base case: empty tree
    }
    
    inorder_traversal(root-&gt;left);   // Process left subtree
    printf("%d ", root-&gt;data);       // Process current node
    inorder_traversal(root-&gt;right);  // Process right subtree
}

void preorder_traversal(Node *root) {
    if (root == NULL) return;
    
    printf("%d ", root-&gt;data);       // Process current first
    preorder_traversal(root-&gt;left);
    preorder_traversal(root-&gt;right);
}

void postorder_traversal(Node *root) {
    if (root == NULL) return;
    
    postorder_traversal(root-&gt;left);
    postorder_traversal(root-&gt;right);
    printf("%d ", root-&gt;data);       // Process current last
}

/* Calculate tree height */
int tree_height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    int left_height = tree_height(root-&gt;left);
    int right_height = tree_height(root-&gt;right);
    
    return 1 + (left_height &gt; right_height ? left_height : right_height);
}

Divide and Conquer

Recursion powers divide-and-conquer algorithms: divide problem into smaller subproblems, solve recursively, combine results. Binary search, merge sort, and quicksort use this approach.

C
/* Binary search (divide and conquer) */
int binary_search(int arr[], int left, int right, int target) {
    /* Base case: Not found */
    if (left &gt; right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    
    /* Base case: Found */
    if (arr[mid] == target) {
        return mid;
    }
    
    /* Recursive cases: Search half */
    if (arr[mid] &gt; target) {
        return binary_search(arr, left, mid - 1, target);  // Search left
    } else {
        return binary_search(arr, mid + 1, right, target);  // Search right
    }
}

/* Power function using divide and conquer */
double power(double base, int exp) {
    /* Base cases */
    if (exp == 0) return 1.0;
    if (exp == 1) return base;
    
    /* Divide: Calculate half power */
    double half = power(base, exp / 2);
    
    /* Conquer: Combine results */
    if (exp % 2 == 0) {
        return half * half;  // Even exponent
    } else {
        return base * half * half;  // Odd exponent
    }
}
// More efficient than multiplying base exp times

Backtracking

Backtracking uses recursion to explore all possibilities, abandoning paths that don't work. It's used for puzzles, game solving, and constraint satisfaction problems.

C
/* Generate all permutations of a string */
void permute(char *str, int left, int right) {
    if (left == right) {
        printf("%s\n", str);  // Base case: Print permutation
        return;
    }
    
    for (int i = left; i <= right; i++) {
        /* Swap */
        char temp = str[left];
        str[left] = str[i];
        str[i] = temp;
        
        /* Recurse on remaining characters */
        permute(str, left + 1, right);
        
        /* Backtrack: Undo swap */
        temp = str[left];
        str[left] = str[i];
        str[i] = temp;
    }
}

/* N-Queens problem (simplified) */
int is_safe(int board[][8], int row, int col, int N) {
    /* Check if queen can be placed at board[row][col] */
    // Check column, diagonals, etc.
    return 1;  // Simplified
}

int solve_n_queens(int board[][8], int col, int N) {
    if (col >= N) {
        return 1;  // All queens placed successfully
    }
    
    for (int row = 0; row < N; row++) {
        if (is_safe(board, row, col, N)) {
            board[row][col] = 1;  // Place queen
            
            if (solve_n_queens(board, col + 1, N)) {
                return 1;  // Solution found
            }
            
            board[row][col] = 0;  // Backtrack: Remove queen
        }
    }
    
    return 0;  // No solution in this path
}

Recursion vs. Iteration

Most recursive problems can be solved iteratively using loops. Choosing between recursion and iteration involves trade-offs: recursion is often clearer for naturally recursive problems but uses more memory and can be slower. Iteration is typically more efficient but may be harder to understand for complex problems.

C
/* When to use RECURSION */
// 1. Problem is naturally recursive (trees, graphs)
// 2. Code clarity is priority
// 3. Depth is bounded and reasonable
// 4. Divide and conquer approach fits

/* When to use ITERATION */
// 1. Performance is critical
// 2. Deep recursion risk (stack overflow)
// 3. Simple counting or accumulation
// 4. Tail recursion that compiler won't optimize

/* Comparison: Greatest Common Divisor (GCD) */

// Recursive (Euclidean algorithm - elegant)
int gcd_recursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd_recursive(b, a % b);
}

// Iterative (efficient)
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/* Performance comparison */
#include <time.h>

void benchmark(void) {
    clock_t start, end;
    
    start = clock();
    for (int i = 0; i < 1000000; i++) {
        factorial(20);  // Recursive
    }
    end = clock();
    printf("Recursive: %f seconds\n", 
           (double)(end - start) / CLOCKS_PER_SEC);
    
    start = clock();
    for (int i = 0; i < 1000000; i++) {
        factorial_iterative(20);  // Iterative
    }
    end = clock();
    printf("Iterative: %f seconds\n",
           (double)(end - start) / CLOCKS_PER_SEC);
}
// Iterative is typically faster

Common Pitfalls

Recursion has specific pitfalls that can crash programs or produce incorrect results. Understanding these helps you write correct recursive functions.

C
/* Pitfall 1: Missing or wrong base case */
int bad_factorial(int n) {
    return n * bad_factorial(n - 1);  // No base case!
}
// Result: Stack overflow

/* Pitfall 2: Base case never reached */
int bad_countdown(int n) {
    if (n == 0) return;
    printf("%d\n", n);
    bad_countdown(n + 1);  // Goes UP, never reaches 0!
}

/* Pitfall 3: Not making progress */
int bad_sum(int n) {
    if (n == 0) return 0;
    return n + bad_sum(n);  // Doesn't decrease n!
}

/* Pitfall 4: Inefficient recursion */
// Don't use naive Fibonacci for large n
// fibonacci(40) takes seconds
// fibonacci(50) takes forever

/* Pitfall 5: Modifying shared state */
int counter = 0;  // Global variable

void bad_recursive(int n) {
    if (n == 0) return;
    counter++;  // Side effect - hard to track
    bad_recursive(n - 1);
}

/* Pitfall 6: Deep recursion */
int deep_sum(int n) {
    if (n == 0) return 0;
    return 1 + deep_sum(n - 1);
}
// deep_sum(1000000) - Stack overflow!

/* Best Practices */

// 1. Always have clear base case
int good_function(int n) {
    if (n <= 0) return BASE_VALUE;  // Clear stopping condition
    return RECURSIVE_CASE;
}

// 2. Ensure progress toward base case
void good_countdown(int n) {
    if (n <= 0) return;
    printf("%d\n", n);
    good_countdown(n - 1);  // Decreases toward 0
}

// 3. Consider iteration for deep recursion
// Use recursion for ~100-1000 calls
// Use iteration for 100,000+ operations

// 4. Use tail recursion when possible
int tail_recursive(int n, int acc) {
    if (n == 0) return acc;
    return tail_recursive(n - 1, acc + n);  // Last operation is recursive call
}

Summary & What's Next

Key Takeaways:

âœ… Recursion: Function calls itself
âœ… Must have base case (stopping condition)
âœ… Must have recursive case (calls itself with smaller problem)
âœ… Uses call stack (memory overhead)
âœ… Natural for trees, divide-and-conquer, backtracking
âœ… Can be elegant but may be slower than iteration
âœ… Risk of stack overflow with deep recursion
âœ… Always ensure progress toward base case

What's Next?

Let's learn about function pointers and callback functions!

Next: Function Pointers â†’