📘 Section 11 — Recursion

A function that calls itself. Solve a big problem by reducing it to a smaller version of the same problem — until you hit a case so small you can answer it directly.

🎯 What You’ll Practice

• Understanding what recursion is and how the call stack works
• Writing a base case and a recursive case
• Tracing recursive calls step-by-step
• Revising functions: sum, digit count, factorial, Fibonacci, palindrome, array printing
• Building a simple calculator that combines several functions

1. What Is Recursion?

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

Every recursive function must have two parts:

1. Base case — the stopping condition. A case so small we can answer it directly, without another recursive call.
2. Recursive case — the function calls itself with a smaller / simpler input, getting closer to the base case.

⚠️ Without a base case, recursion never stops — the program keeps calling itself until the call stack runs out of memory (stack overflow).

General Template Example

returnType functionName(parameters) {
    if (base_case_condition) {
        return base_case_value;          // stop here
    }
    return something + functionName(smaller_input);   // recursive call
}

2. How the Call Hierarchy Works — fact(5)

Let’s trace the classic example: computing the factorial of 5.

The factorial of n (written n!) is the product of all positive integers from 1 up to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. By convention, 0! = 1.

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

Each call pauses and waits for the smaller call below it to finish. When the base case finally returns, the results bubble back up.
Below you will find a lot of ways to trace recursion and know how it works.

Function Calls

Note: It is better to view this diagram on your laptop.

💡 Phase 1 (left, top-down): every call pauses holding onto its multiplication, waiting for the smaller call beneath it. The call stack keeps growing.

💡 Phase 2 (right, bottom-up): once the base case returns 1, each paused call wakes up, plugs the returned value into its multiplication, and returns to its own caller. The stack shrinks back to empty.

💡 Key idea: Each call on the way down just makes a smaller call and pauses. The real work happens on the way back up, once the base case returns a value.

Trace Tables

Read the first table top-to-bottom, then the second table top-to-bottom.

Phase 1 — Going Down (calls pause and wait)

Phase 2 — Coming Back Up (values bubble up)

Substitution Trace

Another way to see it — watch the expression unfold step by step:

fact(5)
= 5 * fact(4)
= 5 * 4 * fact(3)
= 5 * 4 * 3 * fact(2)
= 5 * 4 * 3 * 2 * fact(1)
= 5 * 4 * 3 * 2 * 1 * fact(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 5 * 4 * 3 * 2 * 1
= 5 * 4 * 3 * 2
= 5 * 4 * 6
= 5 * 24
= 120

Call Tree (Branching View)

At every call the function reaches the if, and there are always two possible roads it could take: the base-case road (n == 0) or the recursive road (n * fact(n-1)). Let’s draw both branches at each level. The left branch is the base-case test (an ✗ means “not taken yet”), and the right branch is the recursive call that actually fires until we finally hit n == 0.

          n
       fact(5)
        /          \
      n==0        n * fact(n-1)
       ✗          5 * fact(4)
                   /          \
                 n==0        n * fact(n-1)
                  ✗          4 * fact(3)
                              /          \
                            n==0        n * fact(n-1)
                             ✗          3 * fact(2)
                                         /          \
                                       n==0        n * fact(n-1)
                                        ✗          2 * fact(1)
                                                    /          \
                                                  n==0        n * fact(n-1)
                                                   ✗          1 * fact(0)
                                                               /          \
                                                             n==0        n * fact(n-1)
                                                           return 1          ✗

Read it like this: at each node the function checks n == 0. While n is still bigger than 0, the left branch (n==0) is skipped (✗) and the right branch makes the smaller recursive call. Only at the very bottom, when n finally is 0, does the left branch win and return 1. That returned 1 is what every paused multiplication on the way back up was waiting for.

🧪 Exercises

Exercise 1: Sum of First N Natural Numbers

Task: Write a recursive function to calculate the sum of the first n natural numbers.

#include <stdio.h>

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

int main(){
    int n;
    scanf("%d", &n);
    printf("%d", sum(n));
    return 0;
}

sum(4) = 4 + sum(3)
       = 4 + 3 + sum(2)
       = 4 + 3 + 2 + sum(1)
       = 4 + 3 + 2 + 1 + sum(0)
       = 4 + 3 + 2 + 1 + 0
       = 10

Exercise 2: Count Digits of a Number

Task: Using a recursive function, write a program to calculate the number of digits in an integer.

#include <stdio.h>

int countDigits(int n) {
    if (n == 0)
        return 0;                          // base case
    return 1 + countDigits(n / 10);
}

int main() {
    int num = 12345;
    printf("Number of digits is %d\n", countDigits(num));
    return 0;
}

countDigits(12345) = 1 + countDigits(1234)
                   = 1 + 1 + countDigits(123)
                   = 1 + 1 + 1 + countDigits(12)
                   = 1 + 1 + 1 + 1 + countDigits(1)
                   = 1 + 1 + 1 + 1 + 1 + countDigits(0)
                   = 1 + 1 + 1 + 1 + 1 + 0
                   = 5

Exercise 3: Factorial of N

Task: Using a recursive function, write a program to calculate the factorial of n.

#include <stdio.h>

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

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

Factorial of number 5 is 120

Exercise 4: Palindrome Check (Number)

Task: Using a recursive function, write a program to check if a number is palindrome or not.

// loop without recursion
int reversed = 0;
while (num != 0) {
    reversed = (reversed * 10) + num % 10;
    num /= 10;
}

#include <stdio.h>

int revNum(int num, int rev)
{
    if (num == 0)
        return rev;
    rev = (rev * 10) + (num % 10);
    return revNum(num / 10, rev);
}

int main()
{
    int num;
    scanf("%d", &num);
    if (revNum(num, 0) == num)
        printf("%d is a palindrome.\n", num);
    else
        printf("%d is not a palindrome.\n", num);
    return 0;
}

Exercise 5: Print Array Using Recursion

Task: Write a program to print the elements of an array using recursion.

#include <stdio.h>

void printRec(int arr[], int size, int i){
    if (i == size)
    {
        return;
    }
    printf("%d ", arr[i]);
    printRec(arr, size, i + 1);
    // if you switch this line with the line above,
    // the array will be printed in reverse
}

int main(){
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    printRec(arr, size, 0);
    return 0;
}

1 2 3 4 5

void printRecReverse(int arr[], int size, int i){
    if (i == size) return;
    printRecReverse(arr, size, i + 1);   // recurse first
    printf("%d ", arr[i]);               // print after
}
// Output: 5 4 3 2 1

Exercise 6: Fibonacci

Task: Using a recursive function, write a program that prints the n-th Fibonacci number.

The Fibonacci sequence is defined as:

• fib(0) = 0
• fib(1) = 1

Every other term is simply the sum of its two predecessors

So the sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

🔑 What makes this different? The recursive case makes two calls to itself in the same line. This changes the shape of the call trace — instead of a straight line, it becomes a tree.

#include <stdio.h>

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

int main() {
    int n;
    scanf("%d", &n);
    printf("fib of %d = %d\n", n, fib(n));
    return 0;
}

Enter n: 4
fib of 4 = 3

Substitution Trace for fib(4)

When a function calls itself twice, we can’t just unfold in a straight line — we need parentheses to keep track of which call is being expanded next. On each line, we only expand the leftmost unresolved call; the others sit and wait their turn.

fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + fib(2)
= ((fib(1) + fib(0)) + fib(1)) + fib(2)
= ((1 + fib(0)) + fib(1)) + fib(2)
= ((1 + 0) + fib(1)) + fib(2)
= (1 + fib(1)) + fib(2)
= (1 + 1) + fib(2)
= 2 + fib(2)
= 2 + (fib(1) + fib(0))
= 2 + (1 + fib(0))
= 2 + (1 + 0)
= 2 + 1
= 3

Call Tree for fib(4) (Branching View)

Just like the factorial tree in Section 2, at every call the function reaches the if and there are two roads: the base-case road (n <= 1, returns n) or the recursive road (fib(n-1) + fib(n-2)). The big difference: factorial’s recursive road was a single call, so only one side ever kept going. Fibonacci’s recursive road fires two calls at once — so now both sides keep splitting, and the tree truly branches.

                              n
                           fib(4)
                          /         \
                       n<=1        fib(n-1)  +   fib(n-2)
                        ✗           fib(3)   +    fib(2)
                                  /       \        /    \
                              fib(2)     fib(1)  fib(1) fib(0)
                              /   \       n<=1    n<=1   n<=1
                          fib(1) fib(0)    →1      →1     →0
                          n<=1   n<=1
                           →1     →0

🔑 NOTE The → means return value from this branch in the tree.

Read it like the factorial tree: at each node we test n <= 1. If yes (the left branch), we stop and return n. If no, the right branch fires the two recursive calls, each of which becomes its own little tree.

With the values filled in from the bottom up (every node = its left child + its right child):

                       3
                     /   \
                    2     1
                  /   \  /  \
                 1   1  1    0
                / \
               1   0

🔑 The key contrast: factorial’s “tree” was really a straight chain because only one branch ever recursed. Fibonacci recurses on both branches, so the work doubles at each level — fib(2) even gets computed twice here (look for it on both sides). That repeated work is exactly why naive recursive Fibonacci is slow for large n.

Exercise 7: Simple Calculator

Task: Write a program to perform simple calculator operations. The valid operations are:

The program must contain the following functions:

• A) fact — takes one input and returns the factorial (recursively).
• B) add — performs addition of two numbers.
• C) sub — performs subtraction of two numbers.
• D) mul — performs multiplication of two numbers.
• E) div — performs the division of two numbers.

The program must also check for bad input data (division by zero, negative factorial, invalid choice).

Expected menu:

1: Addition
2: Subtraction
3: Multiplication
4: Division
5: Factorial
6: Quit

#include <stdio.h>

int add(int a, int b) {
    return a + b;
}

int sub(int a, int b) {
    return a - b;
}

int mul(int a, int b) {
    return a * b;
}

double divide(int a, int b) {
    return (double)a / b;
}

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

int main() {
    int c, num1, num2;

    printf("1: Addition\n");
    printf("2: Subtraction\n");
    printf("3: Multiplication\n");
    printf("4: Division\n");
    printf("5: Factorial\n");
    printf("6: Quit\n");

    printf("Enter your operation: ");
    scanf("%d", &c);

    switch (c) {
        case 1:
            printf("Enter two numbers: ");
            scanf("%d %d", &num1, &num2);
            printf("Result: %d\n", add(num1, num2));
            break;
        case 2:
            printf("Enter two numbers: ");
            scanf("%d %d", &num1, &num2);
            printf("Result: %d\n", sub(num1, num2));
            break;
        case 3:
            printf("Enter two numbers: ");
            scanf("%d %d", &num1, &num2);
            printf("Result: %d\n", mul(num1, num2));
            break;
        case 4:
            printf("Enter two numbers: ");
            scanf("%d %d", &num1, &num2);
            if (num2 == 0) {
                printf("Division by zero error\n");
            }
            else {
                printf("Result: %.2f\n", divide(num1, num2));
            }
            break;
        case 5:
            printf("Enter a number: ");
            scanf("%d", &num1);
            if (num1 < 0) {
                printf("Enter a positive number to calculate its factorial\n");
            }
            else {
                printf("Result: %d\n", fact(num1));
            }
            break;
        case 6:
            printf("Goodbye\n");
            break;
        default:
            printf("Incorrect option\n");
    }
    return 0;
}

Enter your operation: 1
Enter two numbers: 2 3
Result: 5

Enter your operation: 5
Enter a number: 5
Result: 120

Enter your operation: 4
Enter two numbers: 10 0
Division by zero error

Exercise 8: Trace the following recursive function

Task: Trace the following recursive function by hand and figure out what it returns for f(18, 12).

📝 Note: This is a famous algorithm called the GCD (Greatest Common Divisor) — it finds the largest number that divides both a and b with no remainder. This particular version is known as the Euclidean algorithm, and it’s one of the oldest algorithms still in use today.

#include <stdio.h>

int f(int a, int b)
{
    if (b == 0) {
        return a;                 // base case
    }
    return f(b, a % b);           // recursive case
}

int main()
{
    printf("%d", f(18, 12));
    return 0;
}

            a   b
          f(18, 12)
           /         \
         b==0       f(b, a%b)
          ✗         f(12, 6)              18 % 12 = 6
                     /         \
                   b==0       f(b, a%b)
                    ✗         f(6, 0)              12 % 6 = 0
                               /         \
                             b==0       f(b, a%b)
                          return 6          ✗     <- b is 0, so the
                                                     LEFT branch wins

f(18, 12)
= f(12, 6)        18 % 12 = 6
= f(6, 0)         12 % 6  = 0
= 6               b == 0, return a

Exercise 9: Disease Spread (Final Challenge) 🦠

Task: A disease spreads as follows: on day 0 there is 1 sick person. Each sick person infects 3 new people the next day (and remains sick themselves). Write a recursive function f(n) that returns the total number of sick people after n days.

🧭 The 4 steps to solve any recursion problem:

1. Explore with examples → compute the first few values by hand and spot the pattern (f(0)=1, f(1)=4, f(2)=13, …).
2. Find the base case → the smallest input you can answer directly, with no recursive call (here, f(0) = 1).
3. Find the recursive case → express the answer for n in terms of the smaller answer f(n-1) (here, f(n) = 3ⁿ + f(n-1)).
4. Assemble the recurrence → snap the base case and recursive case together into one piecewise rule, then verify it by plugging the examples back in.

f(0) = 1
f(1) = 3  + 1  = 4
f(2) = 9  + 4  = 13
f(3) = 27 + 13 = 40

f(0) = 1

f(n) = 3ⁿ + f(n-1)

        ⎧ 1                  if n == 0      (base case)
f(n) =  ⎨
        ⎩ 3ⁿ + f(n - 1)      if n >  0      (recursive case)

f(1) = 3¹ + f(0) = 3 + 1   = 4    ✅
f(2) = 3² + f(1) = 9 + 4   = 13   ✅
f(3) = 3³ + f(2) = 27 + 13 = 40   ✅

#include <stdio.h>
 
int power3(int n) {
    if (n == 0)
        return 1;
    return 3 * power3(n - 1);
}
 
int f(int n) {
    if (n == 0)
        return 1;
    return power3(n) + f(n - 1);
}
 
int main() {
    int n;
    scanf("%d", &n);
    printf("Total sick people after %d days = %d\n", n, f(n));
    return 0;
}

f(3) = 3³ + f(2)
     = 27 + (3² + f(1))
     = 27 + (9  + (3¹ + f(0)))
     = 27 + (9  + (3   + 1))
     = 27 + (9  + 4)
     = 27 + 13
     = 40

Total sick people after 3 days = 40

⬅️ Back to Home