Recursion in C

01What is Recursion?

🔄 Simple Definition

Recursion is when a function calls itself to solve a problem by breaking it down into smaller, similar problems.

🪞 Think of It Like Mirrors

When you stand between two mirrors facing each other, you see infinite reflections — each reflection contains another reflection!

🪞←🧍→🪞

Similarly, a recursive function calls itself, which calls itself, which calls itself... until it stops!

📚 Real-World Examples of Recursion

🪆

Russian Dolls (Matryoshka)

Open a doll → find smaller doll inside → open it → find smaller doll... until the smallest one!

📂

Folder Structure

A folder can contain other folders, which contain other folders... until you reach files!

🌳

Family Tree

Your ancestors: parent → grandparent → great-grandparent... goes back infinitely!

🥦

Broccoli / Fractals

Each branch of broccoli looks like a mini broccoli. The pattern repeats at every scale!

🔢 Mathematical Example: Factorial

The factorial of a number is a perfect example of recursion:

5! = 5 × 4!

4! = 4 × 3!

3! = 3 × 2!

2! = 2 × 1!

1! = 1 (stop here!)

Each factorial is defined in terms of a smaller factorial!

02Two Essential Parts of Every Recursive Function

⚠️ IMPORTANT: Both Parts Are Required!

Without both parts, your recursive function will either run forever (crash!) or never work correctly.

Base Case

📍

What: The condition that STOPS the recursion

🤔

Why: Without it, function calls itself forever!

📝

Think: The smallest Russian doll (no doll inside)

if (n <= 1) {

return 1;

}

Recursive Case

📍

What: Function calls ITSELF with smaller problem

🤔

Why: Breaks big problem into smaller ones

📝

Think: Opening to find the next smaller doll

else {

return n * factorial(n - 1);

}

📝 This program shows a complete recursive function with both parts clearly labeled.

factorial_explained.c

1#include <stdio.h>
2
3// Recursive function to calculate factorial
4int factorial(int n) {
5    
6    // ========== PART 1: BASE CASE ==========
7    // When to STOP calling itself
8    // This prevents infinite recursion!
9    if (n <= 1) {
10        printf("  Base case reached: factorial(%d) = 1\n", n);
11        return 1;  // Stop here, return 1
12    }
13    
14    // ========== PART 2: RECURSIVE CASE ==========
15    // Call itself with a SMALLER problem
16    // n! = n × (n-1)!
17    printf("  Calculating: factorial(%d) = %d × factorial(%d)\n", n, n, n-1);
18    return n * factorial(n - 1);  // Calls itself!
19}
20
21int main() {
22    printf("Calculating factorial(5):\n");
23    printf("========================\n");
24    
25    int result = factorial(5);
26    
27    printf("========================\n");
28    printf("Result: 5! = %d\n", result);
29    
30    return 0;
31}

Output

Calculating factorial(5):

========================

Calculating: factorial(5) = 5 × factorial(4)

Calculating: factorial(4) = 4 × factorial(3)

Calculating: factorial(3) = 3 × factorial(2)

Calculating: factorial(2) = 2 × factorial(1)

Base case reached: factorial(1) = 1

========================

Result: 5! = 120

03How Recursion Uses Stack Memory

📚 What is the Stack?

The stack is a special area in memory that stores information about function calls. Think of it like a stack of plates — you add plates on top and remove from the top!

🍽️ Stack = Stack of Plates

Adding plates (PUSH)

Plate 4 ← Top

Plate 3

Plate 2

Plate 1 ← Bottom

New plates go on TOP

Removing plates (POP)

Plate 4 ← Removed

Plate 3 ← Now Top

Plate 2

Plate 1

Remove from TOP only

🖥️ What is a Stack Frame?

Every time a function is called, C creates a stack frame (like adding a plate). Each stack frame stores:

📦

Local Variables

Variables inside the function

📥

Parameters

Values passed to function

↩️

Return Address

Where to go back after

🔍 Step-by-Step: factorial(3) in Stack Memory

Let's trace exactly what happens in memory when we call factorial(3):

Call factorial(3)

Stack grows ↓

factorial(3)

n = 3

waiting for: 3 × factorial(2)

What happens:

• n=3, not base case (3 > 1)

• Need to calculate 3 × factorial(2)

• Call factorial(2) first!

Call factorial(2)

Stack grows ↓

factorial(2) ← TOP

n = 2

waiting for: 2 × factorial(1)

factorial(3)

n = 3, waiting...

What happens:

• New frame added on top!

• n=2, not base case (2 > 1)

• Need factorial(1) first!

Call factorial(1) — BASE CASE!

Stack at maximum ↓

factorial(1) ← TOP ✓

n = 1

BASE CASE! Returns 1

factorial(2)

waiting...

factorial(3)

waiting...

What happens:

• n=1, THIS IS BASE CASE!

• No more recursive calls

• Returns 1 immediately

• Stack starts unwinding ↑

Return to factorial(2)

Stack shrinks ↑ (POP)

factorial(1) — REMOVED

factorial(2) ← TOP

Got 1 from factorial(1)

Returns: 2 × 1 = 2

factorial(3)

waiting...

What happens:

• factorial(1) frame removed

• factorial(2) gets answer: 1

• Calculates: 2 × 1 = 2

• Returns 2

Return to factorial(3) — FINAL RESULT!

Stack empty! ↑

factorial(2) — REMOVED

factorial(3) ← TOP

Got 2 from factorial(2)

Returns: 3 × 2 = 6

What happens:

• factorial(2) frame removed

• factorial(3) gets answer: 2

• Calculates: 3 × 2 = 6

• Returns 6 — DONE!

💡 Key Insight: LIFO (Last In, First Out)

The last function called is the first to return. factorial(1) was called last but returned first. That's how stacks work!

04See the Stack in Action

📝 This program shows exactly how the stack grows and shrinks during recursion.

stack_visualization.c

1#include <stdio.h>
2
3// Global variable to track recursion depth (for visualization)
4int depth = 0;
5
6// Helper function to print indentation
7void printIndent() {
8    for (int i = 0; i < depth; i++) {
9        printf("  │ ");
10    }
11}
12
13int factorial(int n) {
14    depth++;  // Going deeper into the stack
15    
16    // Show we're entering this function
17    printIndent();
18    printf("📥 PUSH: factorial(%d) - Stack grows!\n", n);
19    
20    // ========== BASE CASE ==========
21    if (n <= 1) {
22        printIndent();
23        printf("🛑 BASE CASE: n=%d, returning 1\n", n);
24        
25        printIndent();
26        printf("📤 POP: factorial(%d) returns 1\n", n);
27        depth--;  // Stack shrinks
28        return 1;
29    }
30    
31    // ========== RECURSIVE CASE ==========
32    printIndent();
33    printf("🔄 Need factorial(%d), calling...\n", n-1);
34    
35    int result = n * factorial(n - 1);  // Recursive call
36    
37    // We're back! Show we're returning
38    printIndent();
39    printf("📤 POP: factorial(%d) returns %d × %d = %d\n", n, n, result/n, result);
40    
41    depth--;  // Stack shrinks
42    return result;
43}
44
45int main() {
46    printf("╔═══════════════════════════════════════════╗\n");
47    printf("║     RECURSION STACK VISUALIZATION         ║\n");
48    printf("╚═══════════════════════════════════════════╝\n\n");
49    
50    printf("Calling factorial(4)...\n\n");
51    
52    int result = factorial(4);
53    
54    printf("\n════════════════════════════════════════════\n");
55    printf("✅ Final Result: 4! = %d\n", result);
56    printf("════════════════════════════════════════════\n");
57    
58    return 0;
59}

Output

╔═══════════════════════════════════════════╗

║ RECURSION STACK VISUALIZATION ║

╚═══════════════════════════════════════════╝

Calling factorial(4)...

│ 📥 PUSH: factorial(4) - Stack grows!

│ 🔄 Need factorial(3), calling...

│ │ 📥 PUSH: factorial(3) - Stack grows!

│ │ 🔄 Need factorial(2), calling...

│ │ │ 📥 PUSH: factorial(2) - Stack grows!

│ │ │ 🔄 Need factorial(1), calling...

│ │ │ │ 📥 PUSH: factorial(1) - Stack grows!

│ │ │ │ 🛑 BASE CASE: n=1, returning 1

│ │ │ │ 📤 POP: factorial(1) returns 1

│ │ │ 📤 POP: factorial(2) returns 2 × 1 = 2

│ │ 📤 POP: factorial(3) returns 3 × 2 = 6

│ 📤 POP: factorial(4) returns 4 × 6 = 24

════════════════════════════════════════════

✅ Final Result: 4! = 24

════════════════════════════════════════════

05Stack Overflow: When Things Go Wrong! 💥

⚠️ What is Stack Overflow?

The stack has limited memory. If recursion goes too deep (too many function calls without returning), the stack runs out of space and the program crashes!

❌ Causes of Stack Overflow

1.Missing base case — function never stops
2.Wrong base case — condition never becomes true
3.Too deep recursion — even with base case

✅ How to Prevent

1.Always have a base case
2.Make sure problem gets smaller each call
3.Use iteration for very deep recursion

📝 This program shows what happens when there's no base case (DON'T RUN THIS!).

stack_overflow.c

1#include <stdio.h>
2
3// ⚠️ DANGER: This will crash!
4// Missing base case = infinite recursion
5
6void infiniteRecursion(int n) {
7    printf("Call #%d - Stack growing...\n", n);
8    
9    // NO BASE CASE! Never stops!
10    infiniteRecursion(n + 1);  // Keeps calling forever
11    
12    // This line is never reached
13    printf("This never prints\n");
14}
15
16// DON'T run this!
17// int main() {
18//     infiniteRecursion(1);
19//     return 0;
20// }
21
22// ✅ CORRECT VERSION:
23void safeRecursion(int n, int limit) {
24    printf("Call #%d\n", n);
25    
26    // BASE CASE: Stop when we reach the limit
27    if (n >= limit) {
28        printf("Base case reached! Stopping.\n");
29        return;
30    }
31    
32    // RECURSIVE CASE: Call with n+1
33    safeRecursion(n + 1, limit);
34}
35
36int main() {
37    printf("Safe recursion with base case:\n");
38    safeRecursion(1, 5);
39    return 0;
40}

Output

Safe recursion with base case:

Call #1

Call #2

Call #3

Call #4

Call #5

Base case reached! Stopping.

06Types of Recursion

Type	Description	Example
Direct Recursion	Function calls itself directly	factorial(n-1)
Indirect Recursion	A calls B, B calls A	funcA() → funcB() → funcA()
Tail Recursion	Recursive call is the LAST operation	return factorial(n-1, acc*n)
Head Recursion	Recursive call is the FIRST operation	factorial(n-1); then process
Tree Recursion	Function makes MULTIPLE recursive calls	fib(n-1) + fib(n-2)

📝 Tail recursion example — the recursive call is the last thing the function does.

recursion_types.c

1#include <stdio.h>
2
3// ========== TAIL RECURSION ==========
4// The recursive call is the LAST operation
5// Can be optimized by compilers (uses less stack)
6
7int factorial_tail(int n, int accumulator) {
8    if (n <= 1) {
9        return accumulator;  // Base case
10    }
11    // Tail call - nothing to do after this returns
12    return factorial_tail(n - 1, n * accumulator);
13}
14
15// Wrapper function for easy use
16int factorial(int n) {
17    return factorial_tail(n, 1);
18}
19
20// ========== TREE RECURSION ==========
21// Function makes MULTIPLE recursive calls (like branches of a tree)
22// Example: Fibonacci
23
24int fibonacci(int n) {
25    if (n <= 1) {
26        return n;  // Base cases: F(0)=0, F(1)=1
27    }
28    // TWO recursive calls - creates a tree!
29    return fibonacci(n - 1) + fibonacci(n - 2);
30}
31
32int main() {
33    printf("=== Tail Recursion (Factorial) ===\n");
34    for (int i = 1; i <= 5; i++) {
35        printf("%d! = %d\n", i, factorial(i));
36    }
37    
38    printf("\n=== Tree Recursion (Fibonacci) ===\n");
39    printf("First 10 Fibonacci numbers:\n");
40    for (int i = 0; i < 10; i++) {
41        printf("F(%d) = %d\n", i, fibonacci(i));
42    }
43    
44    return 0;
45}

Output

=== Tail Recursion (Factorial) ===

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120

=== Tree Recursion (Fibonacci) ===

First 10 Fibonacci numbers:

F(0) = 0

F(1) = 1

F(2) = 1

F(3) = 2

F(4) = 3

F(5) = 5

F(6) = 8

F(7) = 13

F(8) = 21

F(9) = 34

07Recursion vs Iteration: When to Use Which?

Aspect	Recursion	Iteration (Loops)
Memory	Uses more (stack frames)	Uses less
Speed	Usually slower	Usually faster
Code Readability	More elegant for some problems	Can be complex for some problems
Risk	Stack overflow possible	No stack overflow
Best For	Trees, graphs, divide-conquer	Simple counting, arrays

🔄 Use Recursion When:

• Problem has natural recursive structure
• Working with trees/graphs
• Divide-and-conquer algorithms
• Code clarity is priority
• Depth is limited

🔁 Use Iteration When:

• Simple counting or looping
• Performance is critical
• Memory is limited
• Depth is unpredictable
• Problem is naturally iterative

📝 Same problem solved with both recursion and iteration (factorial).

recursion_vs_iteration.c

1#include <stdio.h>
2
3// ========== RECURSIVE VERSION ==========
4int factorial_recursive(int n) {
5    if (n <= 1) return 1;
6    return n * factorial_recursive(n - 1);
7}
8
9// ========== ITERATIVE VERSION ==========
10int factorial_iterative(int n) {
11    int result = 1;
12    for (int i = 2; i <= n; i++) {
13        result *= i;
14    }
15    return result;
16}
17
18int main() {
19    int n = 5;
20    
21    printf("Calculating %d!\n\n", n);
22    
23    printf("Recursive: %d! = %d\n", n, factorial_recursive(n));
24    printf("Iterative: %d! = %d\n", n, factorial_iterative(n));
25    
26    printf("\nBoth give the same answer!\n");
27    printf("But iterative uses less memory.\n");
28    
29    return 0;
30}

Output

Calculating 5!

Recursive: 5! = 120

Iterative: 5! = 120

Both give the same answer!

But iterative uses less memory.

08Common Recursion Mistakes

❌ Mistake 1: Missing Base Case

Without a base case, recursion never stops = stack overflow!

WRONG:

int sum(int n) {
    return n + sum(n-1);
    // Never stops!
}

CORRECT:

int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n-1);
}

❌ Mistake 2: Base Case Never Reached

If the recursive case doesn't move toward the base case, it's still infinite!

WRONG:

int bad(int n) {
    if (n == 0) return 0;
    return bad(n + 1);
    // Goes 5,6,7... never 0!
}

CORRECT:

int good(int n) {
    if (n == 0) return 0;
    return good(n - 1);
    // Goes 5,4,3,2,1,0 ✓
}

❌ Mistake 3: Wrong Return Value

Forgetting to return the recursive result loses the answer!

WRONG:

int factorial(int n) {
    if (n <= 1) return 1;
    n * factorial(n-1);
    // Missing return!
}

CORRECT:

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

❌ Mistake 4: Inefficient Tree Recursion

Fibonacci with simple recursion calculates same values many times!

INEFFICIENT:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1)+fib(n-2);
    // fib(3) calculated many times!
}

BETTER (memoization):

int memo[100] = {0};
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    return memo[n]=fib(n-1)+fib(n-2);
}

09Summary

🎯 Key Takeaways

•Recursion: Function that calls itself to solve smaller sub-problems
•Base Case: Condition to STOP recursion (required!)
•Recursive Case: Function calls itself with smaller problem
•Stack: Memory area that stores function call information
•Stack Frame: Info for one function call (params, local vars, return address)
•LIFO: Last In, First Out - last called function returns first
•Stack Overflow: Crash when recursion goes too deep

12Next Steps

Now that you understand recursion and the stack, explore function pointers!

Next: Function Pointers→Review: Preprocessor

What You Will Learn

01What is Recursion?

🔄 Simple Definition

🪞 Think of It Like Mirrors

📚 Real-World Examples of Recursion

Russian Dolls (Matryoshka)

Folder Structure

Family Tree

Broccoli / Fractals

🔢 Mathematical Example: Factorial

02Two Essential Parts of Every Recursive Function

⚠️ IMPORTANT: Both Parts Are Required!

Base Case

Recursive Case

03How Recursion Uses Stack Memory

📚 What is the Stack?

🍽️ Stack = Stack of Plates

🖥️ What is a Stack Frame?

🔍 Step-by-Step: factorial(3) in Stack Memory

Call factorial(3)

Call factorial(2)

Call factorial(1) — BASE CASE!

Return to factorial(2)

Return to factorial(3) — FINAL RESULT!

💡 Key Insight: LIFO (Last In, First Out)

04See the Stack in Action

05Stack Overflow: When Things Go Wrong! 💥

⚠️ What is Stack Overflow?

❌ Causes of Stack Overflow

✅ How to Prevent

06Types of Recursion

07Recursion vs Iteration: When to Use Which?

🔄 Use Recursion When:

🔁 Use Iteration When:

08Common Recursion Mistakes

❌ Mistake 1: Missing Base Case

❌ Mistake 2: Base Case Never Reached

❌ Mistake 3: Wrong Return Value

❌ Mistake 4: Inefficient Tree Recursion

09Summary

🎯 Key Takeaways

12Next Steps