Recursion (Fundamentals) | Programming Tutorials

A function is allowed to call itself. That sounds like a recipe for going in circles, and it would be, except that each call is given a slightly smaller problem, and eventually the problem becomes so small the answer is obvious. This technique is recursion, and it is the natural way to solve problems that contain smaller copies of themselves: a folder holding folders, a sentence made of smaller sentences, a puzzle that shrinks by one piece each move.

The two parts

Every correct recursive function has:

A base case: an input small enough to answer directly, without another recursive call. It is the stopping condition.
A recursive case: for any larger input, solve it by calling the function on a smaller input and combining the result.

The factorial of n, written n!, is n × (n-1) × ... × 1. Notice that 5! = 5 × 4!. That is the recursive case in one line. The base case is 1! = 1.

Python

def factorial(n):
    if n <= 1:
        return 1                 # base case
    return n * factorial(n - 1)  # recursive case


print("5! =", factorial(5))

JavaScript

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

console.log("5! =", factorial(5));

Java

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

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));
    }
}

#include <stdio.h>

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

int main(void) {
    printf("5! = %ld\n", factorial(5));
    return 0;
}

All four print:

5! = 120

Two checks to make about any recursive function: does every call move toward the base case (here n - 1 gets closer to 1), and does the base case really catch every input that gets there?

Tracing the stack

The call stack from the functions lesson is what makes recursion work. Each call gets its own frame with its own copy of n, so factorial(3) and the factorial(2) it calls do not interfere. The calls pile up on the way down, then answers flow back on the way up. This version prints indented lines to show it.

Python

def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}call factorial({n})")
    if n <= 1:
        print(f"{pad}return 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{pad}return {result}")
    return result


factorial(3)

JavaScript

function factorial(n, depth = 0) {
  const pad = "  ".repeat(depth);
  console.log(`${pad}call factorial(${n})`);
  if (n <= 1) {
    console.log(`${pad}return 1`);
    return 1;
  }
  const result = n * factorial(n - 1, depth + 1);
  console.log(`${pad}return ${result}`);
  return result;
}

factorial(3);

Java

public class FactorialTrace {
    static long factorial(int n, int depth) {
        String pad = "  ".repeat(depth);
        System.out.println(pad + "call factorial(" + n + ")");
        if (n <= 1) {
            System.out.println(pad + "return 1");
            return 1;
        }
        long result = n * factorial(n - 1, depth + 1);
        System.out.println(pad + "return " + result);
        return result;
    }

    public static void main(String[] args) {
        factorial(3, 0);
    }
}

#include <stdio.h>

long factorial(int n, int depth) {
    printf("%*scall factorial(%d)\n", depth * 2, "", n);
    if (n <= 1) {
        printf("%*sreturn 1\n", depth * 2, "");
        return 1;
    }
    long result = n * factorial(n - 1, depth + 1);
    printf("%*sreturn %ld\n", depth * 2, "", result);
    return result;
}

int main(void) {
    factorial(3, 0);
    return 0;
}

The %*s in printf prints an empty string padded to a width, which is a short way to indent.

All four print:

call factorial(3)
  call factorial(2)
    call factorial(1)
    return 1
  return 2
return 6

Follow it: factorial(3) calls factorial(2), which calls factorial(1). That one hits the base case and returns 1. Then factorial(2) finishes its multiplication (2 × 1 = 2) and returns, and factorial(3) computes 3 × 2 = 6. The work is done on the way back up.

A good way to trace by hand is to write the pending calls as a stack, and replace each one with its result as it completes:

factorial(3)
3 * factorial(2)
3 * (2 * factorial(1))
3 * (2 * 1)
3 * 2
6

Stack overflow

Each active call holds a frame, and the stack has a fixed size. If recursion never reaches a base case, or the input is simply too big, the frames use up all the room and the program fails with a stack overflow. The function below has no base case, so it can never stop on its own.

Python

def forever(n):
    return forever(n + 1)


try:
    forever(0)
except RecursionError:
    print("RecursionError: the stack ran out of room")

Output

RecursionError: the stack ran out of room

Python stops the recursion at a limit of about a thousand frames and raises a RecursionError, which is why a recursive function over a million items may need a loop instead.

JavaScript

function forever(n) {
  return forever(n + 1);
}

try {
  forever(0);
} catch (error) {
  console.log(error.name + ": the stack ran out of room");
}

Output

RangeError: the stack ran out of room

JavaScript throws a RangeError when the stack is full.

Java

public class StackOverflow {
    static int forever(int n) {
        return forever(n + 1);
    }

    public static void main(String[] args) {
        try {
            forever(0);
        } catch (StackOverflowError error) {
            System.out.println("StackOverflowError: the stack ran out of room");
        }
    }
}

Output

StackOverflowError: the stack ran out of room

Java throws a StackOverflowError, which a program can technically catch, though it usually should not try.

int forever(int n) {
    return forever(n + 1);
}

/* Calling forever(0) fills the stack until the operating system
   stops the program, usually with "Segmentation fault". */

C has no safe way to demonstrate this. There is no exception to catch, so the program is simply killed, which is why this example is not run.

Recursion over nested data

Recursion shines when the data itself is nested. Take a folder tree where a file is just its size and a folder holds more items. The size of a folder is the sum of the sizes of everything inside, and each of those might be a folder in turn.

root
|-- readme.txt        5
|-- logo.png         40
`-- src
    |-- main.py      20
    |-- util.py      12
    `-- tests
        `-- test_main.py   8

total size = 5 + 40 + 20 + 12 + 8 = 85

The base case is a file (a plain size); the recursive case is a folder, handled by asking about each child. In Python and JavaScript a folder is naturally a dictionary or object of names to contents, so a number tells you it is a file. In Java and C there is no such mixed container, so each item is a small node holding a size and a list of children; a file simply has no children.

Python

tree = {
    "readme.txt": 5,
    "logo.png": 40,
    "src": {
        "main.py": 20,
        "util.py": 12,
        "tests": {"test_main.py": 8},
    },
}


def total_size(node):
    if isinstance(node, int):  # base case: a file
        return node
    return sum(total_size(child) for child in node.values())  # a folder


print("total size:", total_size(tree))

JavaScript

const tree = {
  "readme.txt": 5,
  "logo.png": 40,
  src: {
    "main.py": 20,
    "util.py": 12,
    tests: { "test_main.py": 8 },
  },
};

function totalSize(node) {
  if (typeof node === "number") {   // base case: a file
    return node;
  }
  let total = 0;                    // a folder
  for (const child of Object.values(node)) {
    total += totalSize(child);
  }
  return total;
}

console.log("total size:", totalSize(tree));

Java

import java.util.List;

public class TreeTotal {
    // A file has a size and no children; a folder has children and size 0.
    record Node(int size, List<Node> children) {}

    static Node file(int size) {
        return new Node(size, List.of());
    }

    static Node folder(Node... children) {
        return new Node(0, List.of(children));
    }

    static int totalSize(Node node) {
        int total = node.size();            // a file: its own size (a folder: 0)
        for (Node child : node.children()) {
            total += totalSize(child);      // recursive case: each child
        }
        return total;
    }

    public static void main(String[] args) {
        Node tree = folder(
            file(5),
            file(40),
            folder(file(20), file(12), folder(file(8)))
        );
        System.out.println("total size: " + totalSize(tree));
    }
}

#include <stdio.h>

typedef struct Node {
    int size;                    /* a file's size; 0 for a folder */
    int count;                   /* number of children */
    const struct Node *children;
} Node;

static int total_size(const Node *node) {
    int total = node->size;
    for (int i = 0; i < node->count; i++) {
        total += total_size(&node->children[i]);
    }
    return total;
}

int main(void) {
    static const Node tests[] = {{8, 0, NULL}};
    static const Node src[] = {{20, 0, NULL}, {12, 0, NULL}, {0, 1, tests}};
    static const Node top[] = {{5, 0, NULL}, {40, 0, NULL}, {0, 3, src}};
    Node root = {0, 3, top};
    printf("total size: %d\n", total_size(&root));
    return 0;
}

All four print:

total size: 85

Writing the same thing with a loop is possible but needs you to keep your own stack of folders still to visit. Here, recursion lets the shape of the code match the shape of the data.

Recursion or iteration?

Anything you can do with recursion you can do with a loop, and vice versa. Here is factorial as a loop. It gets 120 again.

Python

def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result


print(factorial_loop(5))

JavaScript

function factorialLoop(n) {
  let result = 1;
  for (let k = 2; k <= n; k++) {
    result *= k;
  }
  return result;
}

console.log(factorialLoop(5));

Java

public class FactorialLoop {
    static long factorialLoop(int n) {
        long result = 1;
        for (int k = 2; k <= n; k++) {
            result *= k;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(factorialLoop(5));
    }
}

#include <stdio.h>

long factorial_loop(int n) {
    long result = 1;
    for (int k = 2; k <= n; k++) {
        result *= k;
    }
    return result;
}

int main(void) {
    printf("%ld\n", factorial_loop(5));
    return 0;
}

All four print 120. Choose between the two on clarity:

Prefer recursion for nested or branching structures (trees, folders, “try each choice and recurse”) and for problems defined in terms of smaller versions of themselves.
Prefer iteration for simple repetition (summing a list, counting), where a loop is shorter, uses less memory and cannot overflow.

Beware naive recursion that repeats work. Computing Fibonacci numbers as fib(n-1) + fib(n-2) recomputes the same values exponentially many times; you will meet techniques such as memoisation later in the track that fix this.

Common pitfalls

Missing or unreachable base case, which leads to a stack overflow.
Not moving toward the base case, for example calling factorial(n) instead of factorial(n - 1).
A base case that misses an input, such as only handling n == 1 and then calling factorial(0), which recurses past it into negative numbers. Using n <= 1 is safer.
Forgetting to return the recursive result. Writing factorial(n - 1) without return throws the answer away.
Recursing on huge inputs where a loop would be safer.
Overflowing the number type. factorial(25) exceeds a 64-bit integer in Java and C. Python integers grow as needed.

ExerciseFactorial, then trace it

Write factorial(n) recursively, then write out by hand the stack of pending multiplications for factorial(4). Input: 4. Expected result: 24.

Show solution

The function is the one shown above. For factorial(4):

factorial(4)
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1)))
4 * (3 * (2 * 1))
4 * (3 * 2)
4 * 6
24

ExercisePower by recursion

Write a recursive power(base, exponent) for whole-number exponents of 0 or more, without using a built-in power operator. Use the fact that base to the exponent is base times base to the exponent - 1. Check these inputs:

base	exponent	Expected
2	10	1024
5	0	1
3	4	81

Show solution

The base case is exponent 0, where the answer is 1. Each call reduces the exponent by one, so every call moves toward it.

Python

def power(base, exponent):
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)


print(power(2, 10))
print(power(5, 0))
print(power(3, 4))

JavaScript

function power(base, exponent) {
  if (exponent === 0) {
    return 1;
  }
  return base * power(base, exponent - 1);
}

console.log(power(2, 10));
console.log(power(5, 0));
console.log(power(3, 4));

Java

public class PowerRec {
    static long power(long base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        return base * power(base, exponent - 1);
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(5, 0));
        System.out.println(power(3, 4));
    }
}

#include <stdio.h>

static long power(long base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    return base * power(base, exponent - 1);
}

int main(void) {
    printf("%ld\n", power(2, 10));
    printf("%ld\n", power(5, 0));
    printf("%ld\n", power(3, 4));
    return 0;
}

All four print:

1024
1
81

ExerciseDirectory size

Use the folder idea from the lesson on this tree: a file a.txt of size 10, and a folder docs that holds b.txt of size 20 and a folder old that holds c.txt of size 5. Write a recursive total_size and print the total. Expected output: 35.

Show solution

The base case is a file, the recursive case is a folder. Only the data differs from the lesson’s example.

Python

def total_size(node):
    if isinstance(node, int):
        return node
    return sum(total_size(child) for child in node.values())


tree = {"a.txt": 10, "docs": {"b.txt": 20, "old": {"c.txt": 5}}}
print(total_size(tree))

JavaScript

function totalSize(node) {
  if (typeof node === "number") {
    return node;
  }
  let total = 0;
  for (const child of Object.values(node)) {
    total += totalSize(child);
  }
  return total;
}

const tree = { "a.txt": 10, docs: { "b.txt": 20, old: { "c.txt": 5 } } };
console.log(totalSize(tree));

Java

import java.util.List;

public class TreeSize {
    record Node(int size, List<Node> children) {}

    static int totalSize(Node node) {
        int total = node.size();
        for (Node child : node.children()) {
            total += totalSize(child);
        }
        return total;
    }

    public static void main(String[] args) {
        Node c = new Node(5, List.of());
        Node old = new Node(0, List.of(c));
        Node b = new Node(20, List.of());
        Node docs = new Node(0, List.of(b, old));
        Node a = new Node(10, List.of());
        Node root = new Node(0, List.of(a, docs));
        System.out.println(totalSize(root));
    }
}

#include <stdio.h>

typedef struct Node {
    int size;
    int count;
    const struct Node *children;
} Node;

static int total_size(const Node *node) {
    int total = node->size;
    for (int i = 0; i < node->count; i++) {
        total += total_size(&node->children[i]);
    }
    return total;
}

int main(void) {
    static const Node old[] = {{5, 0, NULL}};
    static const Node docs[] = {{20, 0, NULL}, {0, 1, old}};
    static const Node top[] = {{10, 0, NULL}, {0, 2, docs}};
    Node root = {0, 2, top};
    printf("%d\n", total_size(&root));
    return 0;
}

All four print 35 (10 + 20 + 5).

ExerciseFind the bug

This function should add up the numbers from 1 to n, but it never stops. What is wrong, and how do you fix it? After the fix, total_to(3) should give 6 and total_to(0) should give 0.

Python

def total_to(n):
    return n + total_to(n - 1)

JavaScript

function totalTo(n) {
  return n + totalTo(n - 1);
}

Java

static int totalTo(int n) {
    return n + totalTo(n - 1);
}

int total_to(int n) {
    return n + total_to(n - 1);
}

Show solution

There is no base case, so the calls continue through 0, -1, -2 and so on until the stack overflows. Add a base case: when n is 0 or less, return 0. Now total_to(3) is 3 + 2 + 1 + 0 = 6.

Python

def total_to(n):
    if n <= 0:
        return 0
    return n + total_to(n - 1)


print(total_to(3))
print(total_to(0))

JavaScript

function totalTo(n) {
  if (n <= 0) {
    return 0;
  }
  return n + totalTo(n - 1);
}

console.log(totalTo(3));
console.log(totalTo(0));

Java

public class TotalTo {
    static int totalTo(int n) {
        if (n <= 0) {
            return 0;
        }
        return n + totalTo(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(totalTo(3));
        System.out.println(totalTo(0));
    }
}

#include <stdio.h>

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

int main(void) {
    printf("%d\n", total_to(3));
    printf("%d\n", total_to(0));
    return 0;
}

All four print 6 then 0.

Summary

A recursive function solves a problem by calling itself on a smaller one, with a base case that stops the process.
Each call has its own frame on the call stack; answers are combined as the calls return.
Missing the base case, or going too deep, causes a stack overflow.
Use recursion for nested structures and loops for simple repetition.

Next: When things go wrong, on error kinds and handling them deliberately.