Functions Continued: Recursion

Recursion is the process in which a function calls itself directly or indirectly. It is a powerful tool for solving problems that can be broken down into identical sub-problems.

10.1 How Recursion Works

A recursive function must have two parts:

1. Base Case: The condition where the recursion stops. Without this, the function will call itself infinitely, causing a Stack Overflow.
2. Recursive Step: The logic that calls the function again with a simplified version of the input.

---

10.2 Example: Factorial with Recursion

The factorial of n (n!) is n * (n-1)!. Base case: 0! = 1.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) // Base Case
        return 1;
    else
        return n * factorial(n - 1); // Recursive Step
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d", num, factorial(num));
    return 0;
}

---

10.3 Example: Fibonacci Series

The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2). Base cases: F(0) = 0, F(1) = 1.

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

---

10.4 Recursion vs iteration

Feature	Recursion	Iteration
Logic	Self-calling	Loop structures (for/while)
Memory	High (uses stack space)	Low
Speed	Relatively slower	Faster
Code Size	Concise and Elegant	More verbose

---

10.5 When to use Recursion?

Recursion is ideal for:

• Tree and Graph traversals.
• Sorting algorithms (Quick Sort, Merge Sort).
• Solving mathematical puzzles like Tower of Hanoi.

Refer to the Lecture Slides for a visual trace of the Fibonacci call tree.