Lesson 4 of 8 · Functions and Arrays · 3 min read · Updated

Recursion

A function that calls itself on a smaller problem — the base case that stops it, and the stack that holds each call.

A recursive function solves a problem by calling itself on a smaller version of it. Every recursive function needs two parts: a base case that answers directly, and a recursive case that moves closer to it.

c
#include <stdio.h>

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

int sum_digits(int n)
{
    if (n == 0) {
        return 0;
    }
    return n % 10 + sum_digits(n / 10);
}

int main(void)
{
    printf("5! = %d\n", factorial(5));
    printf("sum of digits of 4127 = %d\n", sum_digits(4127));
    return 0;
}
Output
5! = 120
sum of digits of 4127 = 14
Each call waits on the stack for the smaller one. factorial(1) answers 1, and the answers multiply back down: 1, then 2, then 6.

The Fibonacci series

c
#include <stdio.h>

int fib(int n)
{
    if (n < 2) {
        return n;                        /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void)
{
    for (int i = 0; i < 10; i++) {
        printf("%d ", fib(i));
    }
    printf("\n");
    return 0;
}
Output
0 1 1 2 3 5 8 13 21 34

Warning

Without a base case — or with one it never reaches, such as calling factorial(-1) with the test n == 1 — the calls never stop, the stack fills up and the program crashes with a stack overflow. Always check the base case first.

Note

Recursion is not faster than a loop — fib(40) this way makes hundreds of millions of calls. Use it when the problem is naturally self-similar: tree structures, folders inside folders, divide-and-conquer sorting. For a simple count, a loop is better.

What must every recursive function have so it can stop?

Try this now

  1. Write a recursive power(base, exp): power(2, 10) should give 1024.
  2. Write a recursive function that prints the digits of a number in reverse: 4127 → 7214.
  3. Write a recursive function that counts down from n to 1 and then prints "Go!".

Create a free account to save your progress, or sign in.