Recursion

Functions that call themselves, base cases, and the Tower of Hanoi.

A recursive function calls itself on a smaller version of the problem. It needs a base case that stops the calls. Without one, it keeps calling until the stack runs out and the program crashes.

#include <stdio.h>

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

int digitSum(int n) {
  if (n < 10) {
    return n;
  }
  return n % 10 + digitSum(n / 10);
}

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

int main(void) {
  printf("%lld\n", factorial(10));
  printf("%d\n", digitSum(2026));
  printf("%d\n", gcd(84, 36));
  return 0;
}

Output

3628800
10
12

Tower of Hanoi

Move n disks from peg A to peg C, one at a time, never putting a bigger disk on a smaller one. The recursive idea: move n - 1 disks out of the way to B, move the biggest disk to C, then move the n - 1 disks from B on top of it.

#include <stdio.h>

int moves = 0;

void hanoi(int n, char from, char to, char via) {
  if (n == 0) {
    return;
  }
  hanoi(n - 1, from, via, to);
  printf("Move disk %d from %c to %c\n", n, from, to);
  moves++;
  hanoi(n - 1, via, to, from);
}

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

Output

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
7 moves

n disks always take 2ⁿ - 1 moves, so 20 disks need over a million. Each call also uses some stack memory. When the depth can be very large, a loop is safer than recursion.

← Strings in C Pointers →