Recursion in C

📖 Introduction

Recursion is a programming technique where a function calls itself to solve a problem. The problem is broken down into smaller subproblems of the same type until reaching a simple base case that can be solved directly.

---

🎯 How Recursion Works

┌────────────────────────────────────────────────────────────────┐
│                    RECURSION CONCEPT                            │
├────────────────────────────────────────────────────────────────┤
│                                                                 │
│   Problem                                                       │
│      │                                                          │
│      ▼                                                          │
│   ┌─────────────────────────────────────────┐                  │
│   │ Is it a base case?                       │                  │
│   └─────────────┬───────────────────────────┘                  │
│                 │                                               │
│        ┌───────┴───────┐                                       │
│        │               │                                        │
│       Yes             No                                        │
│        │               │                                        │
│        ▼               ▼                                        │
│   ┌─────────┐    ┌─────────────────────────┐                   │
│   │ Return  │    │ Solve smaller problem   │                   │
│   │ result  │    │ by calling self         │                   │
│   └─────────┘    └──────────┬──────────────┘                   │
│                             │                                   │
│                             ▼                                   │
│                    Combine results                              │
│                             │                                   │
│                             ▼                                   │
│                       Return                                    │
│                                                                 │
└────────────────────────────────────────────────────────────────┘

---

🔧 Basic Structure

Every recursive function needs:

1. •Base Case(s): Condition to stop recursion
2. •Recursive Case: Call to itself with smaller problem

return_type function_name(parameters) {
    // Base case
    if (base_condition) {
        return base_value;
    }

    // Recursive case
    return function_name(smaller_problem);
}

---

📐 Classic Example: Factorial

Mathematical Definition:

• •0! = 1
• •n! = n × (n-1)!

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

Execution Trace for factorial(4):

factorial(4)
│
├── 4 * factorial(3)
│       │
│       ├── 3 * factorial(2)
│       │       │
│       │       ├── 2 * factorial(1)
│       │       │       │
│       │       │       └── returns 1  (base case)
│       │       │
│       │       └── returns 2 * 1 = 2
│       │
│       └── returns 3 * 2 = 6
│
└── returns 4 * 6 = 24

---

📊 Call Stack Visualization

                Stack grows ↓
┌─────────────────────────────┐
│ factorial(1)  →  returns 1  │  4th call (base case)
├─────────────────────────────┤
│ factorial(2)  →  2 * 1 = 2  │  3rd call
├─────────────────────────────┤
│ factorial(3)  →  3 * 2 = 6  │  2nd call
├─────────────────────────────┤
│ factorial(4)  →  4 * 6 = 24 │  1st call (original)
├─────────────────────────────┤
│ main()                       │
└─────────────────────────────┘

---

🔢 Fibonacci Sequence

Definition:

• •F(0) = 0
• •F(1) = 1
• •F(n) = F(n-1) + F(n-2)

int fibonacci(int n) {
    // Base cases
    if (n <= 0) return 0;
    if (n == 1) return 1;

    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Call Tree for fibonacci(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \       /    \
         fib(3)  fib(2) fib(2) fib(1)
         /   \    / \     / \     |
      fib(2) fib(1) ...   ...    1
       / \     |
    fib(1) fib(0)
       |     |
       1     0

Note: This naive implementation is inefficient (exponential time).

---

🔄 Types of Recursion

1. Direct Recursion:

Function calls itself directly.

void directRecursion() {
    // ...
    directRecursion();  // Calls itself
}

2. Indirect Recursion:

Function A calls function B, which calls function A.

void functionA() {
    // ...
    functionB();
}

void functionB() {
    // ...
    functionA();  // Indirect recursion
}

3. Tail Recursion:

Recursive call is the last operation.

// Tail recursive
int factorial_tail(int n, int accumulator) {
    if (n <= 1) return accumulator;
    return factorial_tail(n - 1, n * accumulator);  // Last operation
}

// Usage:
int result = factorial_tail(5, 1);

4. Head Recursion:

Recursive call happens before other processing.

void headRecursion(int n) {
    if (n <= 0) return;
    headRecursion(n - 1);  // Call first
    printf("%d ", n);      // Process after
}
// Prints: 1 2 3 4 5

---

📚 Common Recursive Problems

1. Sum of Array:

int sumArray(int arr[], int size) {
    if (size <= 0) return 0;
    return arr[size - 1] + sumArray(arr, size - 1);
}

2. Power Function:

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

3. String Reversal:

void printReverse(char str[], int index) {
    if (str[index] == '\0') return;
    printReverse(str, index + 1);
    printf("%c", str[index]);
}

4. Binary Search:

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
    return binarySearch(arr, mid + 1, right, target);
}

5. GCD (Euclidean Algorithm):

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

---

⚖️ Recursion vs Iteration

Factorial: Both Ways

// Recursive
int factorialRecursive(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursive(n - 1);
}

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

---

⚠️ Common Mistakes

1. Missing Base Case:

// WRONG - infinite recursion!
int factorial(int n) {
    return n * factorial(n - 1);
}

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

2. Base Case Never Reached:

// WRONG - n never decreases!
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n);  // Should be n-1
}

3. Stack Overflow:

// This will crash for large n
void stackOverflow(int n) {
    int array[1000];  // Large local variable
    stackOverflow(n + 1);
}

---

🎨 Optimization Techniques

1. Memoization:

Store computed results to avoid recalculating.

int memo[100] = {0};

int fibMemo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];

    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

2. Tail Recursion Optimization:

Compilers can optimize tail-recursive functions.

// Tail recursive - can be optimized
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);
}

// Usage
int result = factorial_tail(5, 1);

---

📐 Recursion Depth

The maximum depth of recursion is limited by stack size.

#include <stdio.h>

int depth = 0;

void measureDepth() {
    depth++;
    if (depth % 10000 == 0) {
        printf("Depth: %d\n", depth);
    }
    measureDepth();  // Will eventually crash
}

// Typical stack allows ~10,000-100,000 calls

---

🔑 Key Takeaways

1. •Every recursion needs a base case - or it runs forever
2. •Each call must move toward the base case
3. •Recursion uses stack memory - can overflow
4. •Some problems are naturally recursive - trees, graphs
5. •Memoization can dramatically improve performance
6. •Tail recursion can be optimized by compilers
7. •Iteration is often more efficient for simple problems

---

⏭️ Next Topic

Continue to Scope and Lifetime to understand how variables behave in different parts of your program.