Topic 5- Recursion

Tags: #◇CCPROG2 #◇C Programming #◇Programming #◇Computer Science #◇Recursion and Iteration #◇Computational Thinking #◇Recursion #◇Algorithm #◇Structured Programming #◇Memory Management

◇Overview

Recursion is the process of a function calling itself to solve a problem by breaking it into smaller sub-problems. Every recursive function needs a base case (termination) and a recursive case (self-call with modified parameters).

◇Key Concepts

Base case: Terminates the recursion — returns a constant or performs no further calls Recursive case: Function calls itself with a smaller/modified problem Recursion uses the call stack — each call gets its own stack frame Procedural (iterative) vs. Functional (recursive) approaches Every recursion can be rewritten iteratively and vice versa

◇Details / Theory

Procedural vs. Functional Approach

Procedural Approach (Iterative — CCPROG1)

1. Step 1
2. Step 2
3. Step 3

Functional Approach (Recursive — CCPROG2)

1. Function call 1
2. Function call 2
3. Function call 3

Factorial — Iterative vs. Recursive

Procedural (Iterative):

int factorial(int N) {
    int prod = 1;
    while (N > 0) {
        prod *= N;
        N--;
    }
    return prod;
}

Functional (Recursive):

int factorial(int N) {
    if (N == 1 || N == 0)   // Base case
        return 1;
    else
        return N * factorial(N - 1);  // Recursive case
}

Trace: factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → 4 * 3 * 2 * factorial(1) → 4 * 3 * 2 * 1 = 24

How to Design a Recursive Function

1. Sketch the solution with varying values of the parameter
2. Identify patterns or common trends → this becomes the recursive case
3. Identify where only 1 or a constant operation is performed → this becomes the base case

Summation — Iterative vs. Recursive

Iterative:

int summation(int a, int b) {
    int sum = 0;
    while (a <= b) {
        sum += a;
        a++;
    }
    return sum;
}

Recursive:

int summation(int a, int b) {
    if (a > b)        // Base case
        return 0;
    return a + summation(a + 1, b);  // Recursive case
}

Display in Order vs. Reverse

Print Ascending (recurse first, then print):

void displayN(int N) {
    if (N > 0) {
        displayN(N - 1);    // Recurse FIRST
        printf("%d\n", N);  // Then print
    }
}

Print Descending (print first, then recurse):

void displayNReverse(int N) {
    if (N > 0) {
        printf("%d\n", N);      // Print FIRST
        displayNReverse(N - 1); // Then recurse
    }
}

The position of the recursive call relative to other statements controls the order of execution.

Power Function

int power(int base, int exp) {
    if (exp == 0)
        return 1;             // Base case: x^0 = 1
    return base * power(base, exp - 1);  // x^n = x * x^(n-1)
}

Fibonacci

int fibonacci(int n) {
    if (n == 0) return 0;     // Base case 1
    if (n == 1) return 1;     // Base case 2
    return fibonacci(n - 1) + fibonacci(n - 2);  // Two recursive calls
}

Warning: Naive Fibonacci has exponential time complexity $O(2^n)$. Use iteration or memoization for efficiency.

The Call Stack

Each recursive call creates a new stack frame with its own local variables. Stack frames are pushed on call and popped on return:

factorial(4)     ← waiting
  factorial(3)   ← waiting
    factorial(2) ← waiting
      factorial(1) → returns 1
    returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

If recursion is too deep, the stack overflows (stack overflow).

◇Common Pitfalls

Missing base case — causes infinite recursion and stack overflow. Base case never reached — recursive call doesn't move toward the base case. Excessive recursion — naive recursive Fibonacci is $O(2^n)$; use iteration or memoization. Confusing print order — print before vs. after the recursive call gives different output order.

◇Summary

TL;DR — Recursion = function calls itself. Every recursive function needs a base case (stop) and a recursive case (smaller sub-problem). Design by tracing values, finding patterns (recursive case), and identifying the simplest case (base case). Watch for stack overflows and efficiency.

◇Links

Related: ◇File Handling — ◇Strings — ◇Structs — ◇Recurrences — ◇Recursion Tree Method — ◇Divide and Conquer Source / Reference:

◇References & Navigation

• Previous Topic: ◇File Handling
• Related Notes: ◇Functions and Programs, ◇Recursion Tree Method