Day 11: Recursion#

Overview#

Recursion is when a function calls itself. It’s a powerful technique for solving problems that have a recursive structure. Today we’ll understand how recursion works, when to use it, and how to avoid common pitfalls.

What We’ll Learn Today#

What is recursion
Base cases and recursive cases
How the call stack works
Writing recursive functions
Classic recursive problems
Recursion vs iteration
Tail recursion

What is Recursion?#

Recursion is when a function calls itself to solve a smaller version of the same problem:

void countdown(int n) {
    if (n <= 0) {
        printf("Blastoff!\n");
        return;  // Base case - stop recursion
    }
    printf("%d\n", n);
    countdown(n - 1);  // Recursive call with smaller problem
}

Why Recursion?#

Some problems have a naturally recursive structure:

Factorials: n! = n × (n-1)!
Fibonacci: fib(n) = fib(n-1) + fib(n-2)
Tree traversal
Divide and conquer algorithms

Base Case vs Recursive Case#

Every recursive function needs TWO parts:

1. Base Case#

The condition that stops recursion:

if (n == 0) {
    return 1;  // Base case - stop here
}

Without a base case, the function recurses forever!

2. Recursive Case#

The function calls itself with a smaller problem:

return n * factorial(n - 1);  // Recursive case

Complete Template#

int recursiveFunction(int n) {
    // 1. Base case - when to stop
    if (n == 0) {
        return someValue;  // Stop recursion
    }

    // 2. Recursive case - call with smaller problem
    return someValue + recursiveFunction(n - 1);
}

Understanding the Call Stack#

Recursion uses the call stack to keep track of function calls:

Visual Example: Factorial#

factorial(5)
  → 5 * factorial(4)
      → 4 * factorial(3)
          → 3 * factorial(2)
              → 2 * factorial(1)
                  → 1 * factorial(0)  ← Base case
                  → return 1
              → return 2 * 1 = 2
          → return 3 * 2 = 6
      → return 4 * 6 = 24
  → return 5 * 24 = 120

Call Stack Visualization#

Call Stack:
┌─────────────────┐
│ factorial(5)    │
├─────────────────┤
│ factorial(4)    │
├─────────────────┤
│ factorial(3)    │
├─────────────────┤
│ factorial(2)    │
├─────────────────┤
│ factorial(1)    │
├─────────────────┤
│ factorial(0)←─ Base case, return 1
└─────────────────┘

Then unwinds:
factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
factorial(5) returns 5 * 24 = 120

Classic Recursion: Factorial#

Problem#

Calculate n! = n × (n-1) × (n-2) × … × 1

Recursive Definition#

Base case: 0! = 1
Recursive case: n! = n × (n-1)!

Implementation#

#include <stdio.h>

int factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }

    // Recursive case
    return n * factorial(n - 1);
}

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

    return 0;
}

Output:

5! = 120
10! = 3628800

Classic Recursion: Fibonacci Sequence#

Problem#

Find the nth Fibonacci number: 1, 1, 2, 3, 5, 8, 13, …

Recursive Definition#

Base case: fib(1) = 1, fib(2) = 1
Recursive case: fib(n) = fib(n-1) + fib(n-2)

Simple Implementation (Inefficient)#

#include <stdio.h>

int fibonacci(int n) {
    // Base cases
    if (n == 1 || n == 2) {
        return 1;
    }

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

int main() {
    printf("fib(1) = %d\n", fibonacci(1));   // 1
    printf("fib(10) = %d\n", fibonacci(10)); // 55
    printf("fib(20) = %d\n", fibonacci(20)); // 6765

    return 0;
}

Why is This Inefficient?#

fibonacci(5) calculates:
fib(5)
  = fib(4) + fib(3)
    = (fib(3) + fib(2)) + (fib(2) + fib(1))
      = ((fib(2) + fib(1)) + 1) + (1 + 1)
      = (1 + 1 + 1) + 3
      = 5

Notice: fib(3) is calculated twice, fib(2) is calculated 3 times!

More Recursive Examples#

Sum of Numbers#

#include <stdio.h>

// Sum of 1 to n
int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

int main() {
    printf("Sum 1 to 5: %d\n", sum(5));   // 15
    printf("Sum 1 to 10: %d\n", sum(10)); // 55

    return 0;
}

Power Function#

#include <stdio.h>

// Calculate x^n
int power(int x, int n) {
    if (n == 0) {
        return 1;  // Any number^0 = 1
    }
    return x * power(x, n - 1);
}

int main() {
    printf("2^5 = %d\n", power(2, 5));   // 32
    printf("3^4 = %d\n", power(3, 4));   // 81

    return 0;
}

Greatest Common Divisor (GCD)#

#include <stdio.h>

// Euclidean algorithm
int gcd(int a, int b) {
    if (b == 0) {
        return a;  // Base case
    }
    return gcd(b, a % b);  // Recursive case
}

int main() {
    printf("GCD(48, 18) = %d\n", gcd(48, 18));  // 6
    printf("GCD(100, 50) = %d\n", gcd(100, 50)); // 50

    return 0;
}

Recursion with Arrays#

Sum of Array Elements#

#include <stdio.h>

int arraySum(int arr[], int n) {
    if (n == 0) {
        return 0;  // Base case
    }
    return arr[n - 1] + arraySum(arr, n - 1);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = 5;

    printf("Sum: %d\n", arraySum(arr, size));  // 15

    return 0;
}

Search in Array#

#include <stdio.h>

int search(int arr[], int n, int target) {
    if (n == 0) {
        return -1;  // Not found
    }

    if (arr[n - 1] == target) {
        return n - 1;  // Found at index n-1
    }

    return search(arr, n - 1, target);  // Search rest
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};

    printf("Index of 30: %d\n", search(arr, 5, 30));  // 2
    printf("Index of 100: %d\n", search(arr, 5, 100)); // -1

    return 0;
}

Recursion vs Iteration#

Factorial - Recursive#

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

Factorial - Iterative#

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

When to Use Which?#

Recursion	Iteration
Natural recursive structure	Loops are natural
Easier to understand	Better performance
More elegant code	Less memory usage
Deeper call stacks	No stack overflow risk

Common Recursion Mistakes#

Mistake 1: Missing or Wrong Base Case#

// ❌ Wrong - infinite recursion
int countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);  // No base case!
}

// ✅ Correct
int countdown(int n) {
    if (n <= 0) return;  // Base case
    printf("%d\n", n);
    countdown(n - 1);
}

Mistake 2: Not Moving Toward Base Case#

// ❌ Wrong - n never changes
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n);  // Always same n!
}

// ✅ Correct
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);  // n decreases
}

Mistake 3: Stack Overflow#

// Large n can cause stack overflow
factorial(1000000);  // Too deep!

Tail Recursion Optimization#

A recursive call is the last operation:

// Tail recursion
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // Last call
}

// Usage
factorial_tail(5, 1);  // Pass accumulator

Some compilers optimize tail recursion to iteration automatically.

Practical Example: Binary Search#

#include <stdio.h>

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

    int mid = (left + right) / 2;

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

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int size = 8;

    printf("Index of 7: %d\n", binarySearch(arr, 0, size - 1, 7));    // 3
    printf("Index of 11: %d\n", binarySearch(arr, 0, size - 1, 11));  // 5
    printf("Index of 20: %d\n", binarySearch(arr, 0, size - 1, 20));  // -1

    return 0;
}

Practice Exercises#

Exercise 1: Palindrome Check#

Write a recursive function that checks if a string is a palindrome.

Exercise 2: Count Occurrences#

Write a recursive function that counts how many times a number appears in an array.

Exercise 3: Reverse String#

Write a recursive function that reverses a string.

Exercise 4: Generate Combinations#

Write a function that generates all combinations of a set.

Summary#

✅ Understood base cases and recursive cases
✅ Learned how the call stack works
✅ Implemented classic algorithms recursively
✅ Worked with arrays recursively
✅ Compared recursion vs iteration
✅ Avoided common mistakes
✅ Optimized with tail recursion

Key Points to Remember#

Every recursion needs a base case
Each recursive call must move toward the base case
The call stack tracks all function calls
Recursion is elegant but can be memory-intensive
Use recursion for naturally recursive problems
Check for stack overflow with deep recursion
Base case is the most important part

Next Steps#

Tomorrow we’ll learn about file handling - reading from and writing to files!

→ Continue to Day 12

← Back to Day 10