Recursion

Recursion

Recursion is when a function calls itself. It's a powerful way to solve problems that can be split into smaller copies of themselves.

A classic: factorials

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

factorial(4) = 4 x 3 x 2 x 1 = 24.

How it works

factorial(4) calls factorial(3), which calls factorial(2), and so on, down to the base case n <= 1. Then the answers multiply back up.

Two required parts

1. Base case - stops the recursion (here, n <= 1).
2. Recursive step - calls itself with a smaller input.

Danger

Without a base case, recursion runs forever and crashes the stack.

TL;DR

• Recursion = a function calling itself.
• Needs a base case to stop.
• The recursive step must shrink the problem.
• No base case = infinite recursion.