Recursion in C

A recursive function solves a problem by calling itself on a smaller version of the same problem. Some problems – walking a folder tree, Tower of Hanoi, many sorting and searching algorithms – are much easier to express this way. Recursion questions are guaranteed in C viva exams and coding rounds.

The two parts of every recursive function

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) return 1;                 // base case: stops the recursion
    return n * factorial(n - 1);          // recursive case: a smaller problem
}

int main(void) {
    for (int n = 0; n <= 6; n++) printf("%d! = %llu\n", n, factorial(n));
    printf("15! = %llu\n", factorial(15));
    return 0;
}

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
15! = 1307674368000

Each call waits on the stack until the call below it returns. Without a base case – or if the problem never gets smaller – the calls never stop and the program crashes with a stack overflow.

Seeing the order of calls

#include <stdio.h>

void count(int n) {
    if (n == 0) return;
    printf("going down: %d\n", n);       // runs before the recursive call
    count(n - 1);
    printf("coming back: %d\n", n);      // runs after it returns
}

int main(void) {
    count(3);
    return 0;
}

going down: 3
going down: 2
going down: 1
coming back: 1
coming back: 2
coming back: 3

Code before the recursive call runs on the way down; code after it runs on the way back up – in reverse order. That's how recursion can print things backwards.

More classic recursive functions

#include <stdio.h>

int sum_digits(int n)        { return n == 0 ? 0 : n % 10 + sum_digits(n / 10); }
int gcd(int a, int b)        { return b == 0 ? a : gcd(b, a % b); }
long long power(int b, int e) {                     // fast power: halves e each call
    if (e == 0) return 1;
    long long half = power(b, e / 2);
    return e % 2 == 0 ? half * half : half * half * b;
}
void print_binary(int n) {
    if (n > 1) print_binary(n / 2);
    printf("%d", n % 2);
}

int main(void) {
    printf("sum_digits(98765) = %d\n", sum_digits(98765));
    printf("gcd(84, 36) = %d\n", gcd(84, 36));
    printf("power(3, 13) = %lld\n", power(3, 13));
    printf("binary of 45 = "); print_binary(45); printf("\n");
    return 0;
}

sum_digits(98765) = 35
gcd(84, 36) = 12
power(3, 13) = 1594323
binary of 45 = 101101

Tower of Hanoi

Move n discs from peg A to peg C using peg B, never placing a larger disc on a smaller one. The recursive idea: move n−1 discs out of the way, move the biggest disc, then move the n−1 discs on top of it.

#include <stdio.h>

int moves = 0;

void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);          // move n-1 discs out of the way
    printf("Move disc %d from %c to %c\n", n, from, to);
    moves++;
    hanoi(n - 1, via, from, to);          // put them back on top
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    printf("Total moves: %d (2^3 - 1)\n", moves);
    return 0;
}

Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
Total moves: 7 (2^3 - 1)

Recursion vs loops

#include <stdio.h>

int calls = 0;
long long fib_recursive(int n) {          // simple but very slow: recomputes the same values
    calls++;
    return n < 2 ? n : fib_recursive(n - 1) + fib_recursive(n - 2);
}

long long fib_loop(int n) {               // fast: each value computed once
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) { long long t = a + b; a = b; b = t; }
    return a;
}

int main(void) {
    printf("fib(25) recursive = %lld using %d calls\n", fib_recursive(25), calls);
    printf("fib(25) loop      = %lld\n", fib_loop(25));
    printf("fib(80) loop      = %lld\n", fib_loop(80));
    return 0;
}

fib(25) recursive = 75025 using 242785 calls
fib(25) loop      = 75025
fib(80) loop      = 23416728348467685

Practice

Summary

Interview practice: C functions interview questions.