Chapter 4 · Lesson 2

Recursion

Recursion in C

A function that calls itself is recursive. Every recursive solution needs two parts:

Base case The condition that stops the recursion. Without it, the function calls itself forever, eventually causing a stack overflow.

Recursive case The function calls itself with a simpler/smaller input, moving toward the base case.

The call stack Each function call is a new stack frame with its own local variables. Deep recursion consumes stack memory proportional to the recursion depth.

Classic examples

Factorial: n! = n * (n-1)!, base case 0! = 1
Fibonacci: fib(n) = fib(n-1) + fib(n-2), base cases fib(0)=0, fib(1)=1

Key points:

Always identify the base case first.
Ensure the recursive call makes progress toward the base case.
Naive Fibonacci is O(2^n) — use iteration or memoization for large n.
Tail-recursive functions can sometimes be optimised by the compiler into loops.

Code Examples

Factorial and Fibonaccic

#include <stdio.h>

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

int fibonacci(int n) {
    if (n <= 0) return 0;           // base case
    if (n == 1) return 1;           // base case
    return fibonacci(n-1) + fibonacci(n-2);
}

int main(void) {
    for (int i = 0; i <= 7; i++) {
        printf("%d! = %ld\n", i, factorial(i));
    }
    printf("\nFibonacci: ");
    for (int i = 0; i < 8; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

Each recursive call reduces the problem size. The call stack unwinds when the base case is reached.

Binary search (recursive)c

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) return -1;          // base case: not found

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) return mid; // base case: found
    if (arr[mid] < target)
        return binarySearch(arr, mid + 1, high, target);
    else
        return binarySearch(arr, low, mid - 1, target);
}

int main(void) {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = 10;

    int idx = binarySearch(arr, 0, n - 1, 23);
    printf("23 found at index: %d\n", idx);

    idx = binarySearch(arr, 0, n - 1, 10);
    printf("10 found at index: %d\n", idx);
    return 0;
}

Binary search halves the search space each call (O(log n)). Each recursive call passes a smaller sub-array range.

Quick Quiz

1. What causes a stack overflow in a recursive function?

2. What are the two required parts of a recursive function?

Was this lesson helpful?