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);

}

▶ Try it: 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

▶ Try it: 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

Warning: 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.

!Code Pitfalls: Common Mistakes & What to Watch For

These are the most common mistakes that trip up beginners. Study them carefully to avoid hours of debugging!

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);
}

09More Practical Examples

Here are more useful recursive functions you'll encounter in programming:

more_recursion_examples.c

1#include <stdio.h>
2
3// ===== 1. POWER FUNCTION =====
4// Calculate x^n recursively
5// x^n = x * x^(n-1)
6// Base case: x^0 = 1
7int power(int base, int exp) {
8    if (exp == 0) return 1;                    // Base case
9    return base * power(base, exp - 1);        // Recursive case
10}
11
12// ===== 2. GCD (Greatest Common Divisor) =====
13// Euclidean algorithm: gcd(a, b) = gcd(b, a % b)
14// Base case: gcd(a, 0) = a
15int gcd(int a, int b) {
16    if (b == 0) return a;                      // Base case
17    return gcd(b, a % b);                      // Recursive case
18}
19
20// ===== 3. SUM OF DIGITS =====
21// sum(1234) = 4 + sum(123) = 4 + 3 + sum(12) = ...
22// Base case: single digit number
23int sumOfDigits(int n) {
24    if (n < 10) return n;                      // Base case: single digit
25    return (n % 10) + sumOfDigits(n / 10);     // Last digit + sum of rest
26}
27
28// ===== 4. REVERSE A STRING =====
29// Swap first and last, then reverse middle
30void reverseString(char str[], int start, int end) {
31    if (start >= end) return;                  // Base case: nothing to swap
32    
33    // Swap characters
34    char temp = str[start];
35    str[start] = str[end];
36    str[end] = temp;
37    
38    reverseString(str, start + 1, end - 1);    // Recursive case
39}
40
41// ===== 5. COUNT OCCURRENCES =====
42// Count how many times a character appears in string
43int countChar(char str[], char ch, int index) {
44    if (str[index] == '\0') return 0;          // Base case: end of string
45    
46    int count = (str[index] == ch) ? 1 : 0;
47    return count + countChar(str, ch, index + 1);
48}
49
50int main() {
51    printf("===== Power Function =====\n");
52    printf("2^10 = %d\n", power(2, 10));
53    printf("3^4 = %d\n", power(3, 4));
54    
55    printf("\n===== GCD =====\n");
56    printf("gcd(48, 18) = %d\n", gcd(48, 18));
57    printf("gcd(54, 24) = %d\n", gcd(54, 24));
58    
59    printf("\n===== Sum of Digits =====\n");
60    printf("sumOfDigits(1234) = %d\n", sumOfDigits(1234));
61    printf("sumOfDigits(9876) = %d\n", sumOfDigits(9876));
62    
63    printf("\n===== Reverse String =====\n");
64    char str[] = "Hello";
65    printf("Before: %s\n", str);
66    reverseString(str, 0, 4);
67    printf("After:  %s\n", str);
68    
69    printf("\n===== Count Character =====\n");
70    char text[] = "mississippi";
71    printf("'s' in '%s': %d times\n", text, countChar(text, 's', 0));
72    printf("'i' in '%s': %d times\n", text, countChar(text, 'i', 0));
73    
74    return 0;
75}

Output

===== Power Function =====

2^10 = 1024

3^4 = 81

===== GCD =====

gcd(48, 18) = 6

gcd(54, 24) = 6

===== Sum of Digits =====

sumOfDigits(1234) = 10

sumOfDigits(9876) = 30

===== Reverse String =====

Before: Hello

After: olleH

===== Count Character =====

's' in 'mississippi': 4 times

'i' in 'mississippi': 4 times

Pattern Recognition

Notice how each function follows the same pattern:

1. Check base case — return simple answer
2. Make problem smaller — recursive call
3. Combine results — build up the answer

Watch Out When Copying Code!

Key Takeaways

•Recursion: Function that calls itself
•Base Case: Condition to STOP
•Recursive Case: Make problem smaller
•Stack: Stores function calls (LIFO)

•Stack Frame: One function's data
•Stack Overflow: Too deep recursion
•Tail Recursion: Optimizable pattern
•Tree Recursion: Multiple recursive calls

Quick Reference

Factorial

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

Fibonacci

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

Power

int pow(int x, int n) {
  if (n == 0) return 1;
  return x * pow(x, n-1);
}

GCD

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

When to Use Recursion

✓Good for:

• Tree/graph traversal
• Divide-and-conquer algorithms
• Mathematical definitions (factorial)
• Backtracking problems

Avoid when:

• Simple iteration works
• Very deep recursion expected
• Performance is critical
• Memory is limited

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);

}

▶ Try it: 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

▶ Try it: 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

Warning: 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.

!Code Pitfalls: Common Mistakes & What to Watch For

These are the most common mistakes that trip up beginners. Study them carefully to avoid hours of debugging!

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);
}

09More Practical Examples

Here are more useful recursive functions you'll encounter in programming:

more_recursion_examples.c

1#include <stdio.h>
2
3// ===== 1. POWER FUNCTION =====
4// Calculate x^n recursively
5// x^n = x * x^(n-1)
6// Base case: x^0 = 1
7int power(int base, int exp) {
8    if (exp == 0) return 1;                    // Base case
9    return base * power(base, exp - 1);        // Recursive case
10}
11
12// ===== 2. GCD (Greatest Common Divisor) =====
13// Euclidean algorithm: gcd(a, b) = gcd(b, a % b)
14// Base case: gcd(a, 0) = a
15int gcd(int a, int b) {
16    if (b == 0) return a;                      // Base case
17    return gcd(b, a % b);                      // Recursive case
18}
19
20// ===== 3. SUM OF DIGITS =====
21// sum(1234) = 4 + sum(123) = 4 + 3 + sum(12) = ...
22// Base case: single digit number
23int sumOfDigits(int n) {
24    if (n < 10) return n;                      // Base case: single digit
25    return (n % 10) + sumOfDigits(n / 10);     // Last digit + sum of rest
26}
27
28// ===== 4. REVERSE A STRING =====
29// Swap first and last, then reverse middle
30void reverseString(char str[], int start, int end) {
31    if (start >= end) return;                  // Base case: nothing to swap
32    
33    // Swap characters
34    char temp = str[start];
35    str[start] = str[end];
36    str[end] = temp;
37    
38    reverseString(str, start + 1, end - 1);    // Recursive case
39}
40
41// ===== 5. COUNT OCCURRENCES =====
42// Count how many times a character appears in string
43int countChar(char str[], char ch, int index) {
44    if (str[index] == '\0') return 0;          // Base case: end of string
45    
46    int count = (str[index] == ch) ? 1 : 0;
47    return count + countChar(str, ch, index + 1);
48}
49
50int main() {
51    printf("===== Power Function =====\n");
52    printf("2^10 = %d\n", power(2, 10));
53    printf("3^4 = %d\n", power(3, 4));
54    
55    printf("\n===== GCD =====\n");
56    printf("gcd(48, 18) = %d\n", gcd(48, 18));
57    printf("gcd(54, 24) = %d\n", gcd(54, 24));
58    
59    printf("\n===== Sum of Digits =====\n");
60    printf("sumOfDigits(1234) = %d\n", sumOfDigits(1234));
61    printf("sumOfDigits(9876) = %d\n", sumOfDigits(9876));
62    
63    printf("\n===== Reverse String =====\n");
64    char str[] = "Hello";
65    printf("Before: %s\n", str);
66    reverseString(str, 0, 4);
67    printf("After:  %s\n", str);
68    
69    printf("\n===== Count Character =====\n");
70    char text[] = "mississippi";
71    printf("'s' in '%s': %d times\n", text, countChar(text, 's', 0));
72    printf("'i' in '%s': %d times\n", text, countChar(text, 'i', 0));
73    
74    return 0;
75}

Output

===== Power Function =====

2^10 = 1024

3^4 = 81

===== GCD =====

gcd(48, 18) = 6

gcd(54, 24) = 6

===== Sum of Digits =====

sumOfDigits(1234) = 10

sumOfDigits(9876) = 30

===== Reverse String =====

Before: Hello

After: olleH

===== Count Character =====

's' in 'mississippi': 4 times

'i' in 'mississippi': 4 times

Pattern Recognition

Notice how each function follows the same pattern:

1. Check base case — return simple answer
2. Make problem smaller — recursive call
3. Combine results — build up the answer

Watch Out When Copying Code!

Key Takeaways

•Recursion: Function that calls itself
•Base Case: Condition to STOP
•Recursive Case: Make problem smaller
•Stack: Stores function calls (LIFO)

•Stack Frame: One function's data
•Stack Overflow: Too deep recursion
•Tail Recursion: Optimizable pattern
•Tree Recursion: Multiple recursive calls

Quick Reference

Factorial

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

Fibonacci

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

Power

int pow(int x, int n) {
  if (n == 0) return 1;
  return x * pow(x, n-1);
}

GCD

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

When to Use Recursion

✓Good for:

• Tree/graph traversal
• Divide-and-conquer algorithms
• Mathematical definitions (factorial)
• Backtracking problems

Avoid when:

• Simple iteration works
• Very deep recursion expected
• Performance is critical
• Memory is limited

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:

!Code Pitfalls: Common Mistakes & What to Watch For

Mistake 1: Missing Base Case

Mistake 2: Base Case Never Reached

Mistake 3: Wrong Return Value

Mistake 4: Inefficient Tree Recursion

09More Practical Examples

Pattern Recognition

Watch Out When Copying Code!

Key Takeaways

Quick Reference

When to Use Recursion

Test Your Knowledge

Related Tutorials

Functions in C

C Program Memory Layout

Structures in C

Have Feedback?

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