Lesson 6 — Recursion — C Programming

📖

What Is Recursion?

A recursive function is a function that calls itself to solve a smaller version of the same problem. Every recursive function needs two parts, or it will never stop:

Base case — the simplest input, answered directly, with no further recursive call. This is what stops the recursion.
Recursive case — breaks the problem into a smaller version of itself, and calls the function again on that smaller piece.

anatomy of a recursive function

if (n == 0) return 1;

① Base case — stops recursion

else

return n * fact(n-1);

② Recursive case — smaller subproblem

fact(4) → 4 * fact(3) → 3 * fact(2) → 2 * fact(1) → 1 * fact(0) fact(0) = 1 ← base case reached, stack stops growing ← returns 1 * 1 = 1 ← returns 2 * 1 = 2 ← returns 3 * 2 = 6 ← returns 4 * 6 = 24

💡 Every call waits. Each call to fact(n) pauses at n * fact(n-1) and waits for the inner call to return — this is exactly how the C function call stack works, one frame per active call.

1

Factorial — Your First Recursive Function

Single recursive call

Factorial is defined recursively by nature: n! = n × (n-1)!, with 0! = 1 as the base case. This maps almost word-for-word into C.

Example 1 · factorial.c

factorial.c

C

#include <stdio.h>

int factorial(int n) {
    if (n == 0)          // base case
        return 1;
    return n * factorial(n - 1);  // recursive case
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);

    printf("%d! = %d\n", n, factorial(n));
    return 0;
}

terminal

output

Enter a number: 5
5! = 120

Line by line:

if (n == 0) return 1; — without this line, the function would call itself forever and crash with a stack overflow
n * factorial(n - 1) — each call does one multiplication and hands off a smaller problem
The multiplications only happen once every call has returned, working backward from factorial(0)

⚠️ Forgetting the base case is the #1 recursion bug. The call stack grows until the program crashes with a stack overflow — always write the base case first, before the recursive case.

2

Recursion on Arrays

Sum & reverse-print

Recursion works on arrays by shrinking the index range each call instead of shrinking a number. "Sum of array from index i to end" is a smaller version of "sum of array from index i-1 to end."

Example 2 · array_recursion.c

array_recursion.c

C

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n == 0)                  // base case: empty range
        return 0;
    return arr[n - 1] + sumArray(arr, n - 1);
}

void printReverse(int arr[], int index, int n) {
    if (index == n)                // base case: past the last element
        return;
    printReverse(arr, index + 1, n);   // go deeper first...
    printf("%d ", arr[index]);        // ...then print while unwinding
}

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

    printf("Sum = %d\n", sumArray(arr, n));

    printf("Reversed: ");
    printReverse(arr, 0, n);
    printf("\n");

    return 0;
}

terminal

output

Sum = 150
Reversed: 50 40 30 20 10

💡 printReverse's trick: it recurses to the end of the array before printing anything. Since each call prints only after its own recursive call returns, the printing happens in reverse order automatically — no extra array needed.

3

Fibonacci — Two Recursive Calls

Recursion tree & efficiency

Fibonacci is defined as fib(n) = fib(n-1) + fib(n-2). Unlike factorial, each call branches into two more calls — the recursion tree grows exponentially, and the same values get recomputed many times.

fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0) fib(2) is computed TWICE — this repetition is what makes plain recursion slow

Example 3 · fibonacci.c

fibonacci.c

C

#include <stdio.h>

int fib(int n) {
    if (n == 0) return 0;   // base case 1
    if (n == 1) return 1;   // base case 2
    return fib(n - 1) + fib(n - 2);  // two recursive calls
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);

    printf("Fibonacci series: ");
    for (int i = 0; i <= n; i++)
        printf("%d ", fib(i));
    printf("\n");

    return 0;
}

terminal

output

Enter n: 8
Fibonacci series: 0 1 1 2 3 5 8 13 21

⚠️ fib(40) takes billions of calls. Plain recursive Fibonacci is O(2ⁿ) because it recomputes the same subproblems repeatedly. The fix — storing already-computed results — is called memoization, and it's the entry point into dynamic programming.

4

Tower of Hanoi

Classic multi-call recursion

Move n disks from rod A to rod C, using rod B as a helper, never placing a bigger disk on a smaller one. The recursive insight: to move n disks, first move the top n-1 disks out of the way, move the big one, then move those n-1 disks back on top.

Example 4 · tower_of_hanoi.c

tower_of_hanoi.c

C

#include <stdio.h>

void hanoi(int n, char from, char aux, char to) {
    if (n == 0)               // base case: nothing to move
        return;

    hanoi(n - 1, from, to, aux);   // 1. move n-1 disks out of the way
    printf("Move disk %d from %c to %c\n", n, from, to); // 2. move the big disk
    hanoi(n - 1, aux, from, to);   // 3. move n-1 disks back on top
}

int main() {
    int disks;
    printf("Enter number of disks: ");
    scanf("%d", &disks);

    hanoi(disks, 'A', 'B', 'C');
    return 0;
}

terminal — disks=3

output

Enter number of disks: 3
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Disks (n)	Minimum moves	Formula
3	7	2ⁿ − 1
5	31	2ⁿ − 1
10	1023	2ⁿ − 1

5

Recursion vs Iteration

Same problem, two approaches

Anything recursion can do, a loop can also do — the question is readability vs memory. Recursion often reads closer to the mathematical definition; iteration avoids the memory cost of the call stack.

Example 5 · sum_compare.c

sum_compare.c

C

#include <stdio.h>

// Recursive version
int sumRecursive(int n) {
    if (n == 0) return 0;
    return n + sumRecursive(n - 1);
}

// Iterative version — no call stack growth
int sumIterative(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++)
        total += i;
    return total;
}

int main() {
    int n = 5;
    printf("Recursive sum(%d) = %d\n", n, sumRecursive(n));
    printf("Iterative sum(%d) = %d\n", n, sumIterative(n));
    return 0;
}

terminal

output

Recursive sum(5) = 15
Iterative sum(5) = 15

Aspect	Recursion	Iteration
Memory	Uses call stack — O(n) extra space	O(1) extra space
Readability	Often matches the mathematical definition	Can be less obvious for tree/graph problems
Speed	Slightly slower — function call overhead	Usually faster
Best for	Trees, graphs, divide-and-conquer, backtracking	Simple counting, linear scans

💡 Tail recursion is when the recursive call is the very last thing a function does (like sumRecursive above, if rewritten to pass a running total). Some compilers optimize this into a loop automatically — but standard C makes no such guarantee, so don't rely on it for very deep recursion.

Q

Quick Quiz

Question 1 of 5

What happens if a recursive function has no base case?

Question 2 of 5

In factorial(n), what is the base case?

Question 3 of 5

Why is plain recursive Fibonacci slow for large n?

Question 4 of 5

For n disks, the Tower of Hanoi needs a minimum of how many moves?

Question 5 of 5

Compared to iteration, what does recursion typically cost more of?

✓

Lesson Checklist

I understand base case vs recursive case
I can write factorial using recursion
I can trace how the call stack grows and unwinds
I can sum an array recursively by shrinking the index
I understand why printReverse prints in reverse order
I understand why Fibonacci recursion recomputes work
I can write and trace Tower of Hanoi
I know when to prefer recursion vs iteration
I know what tail recursion means
I completed the quiz

→

Next: Lesson 7 — Searching Algorithms

Coming up

🔍 Linear Search Lesson 7
⚡ Binary Search — iterative & recursive Lesson 7
📊 Time complexity comparison Lesson 7
🧩 Searching in a sorted vs unsorted array Lesson 7

Recursion — A Function Calling Itself

What Is Recursion?

anatomy of a recursive function

Factorial — Your First Recursive Function

Recursion on Arrays

Fibonacci — Two Recursive Calls

Tower of Hanoi

Recursion vs Iteration

Quick Quiz

Lesson Checklist

Next: Lesson 7 — Searching Algorithms