Lesson 12.1 · Recursion

Thinking Recursively

Every recursive function has a base case that stops, and a recursive case that shrinks the problem and trusts the smaller call to be correct.

14 min

Think of it like this

Standing in a long queue and wanting to know your position, you ask the person in front: "what's your position?". They ask the person in front of them, and so on, until the first person says "1". Each answer comes back one plus the previous. Nobody needs to see the whole queue.

1.The two parts

Base case: the smallest input you can answer directly, with no further calls (n == 0, empty string, null node). Without it, the calls never stop.

Recursive case: express the answer using a call on a smaller input, and combine. The input must get strictly closer to the base case every time.

Factorial.java

public class Main {
    static long factorial(int n) {
        if (n <= 1) return 1;              // base case
        return n * factorial(n - 1);       // recursive case: trust factorial(n - 1)
    }
    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial(20));
    }
}

Output

120
2432902008176640000

2.The leap of faith

Don't trace every level in your head. Assume the call on the smaller input returns the right answer, and check only two things: the base case is right, and combining the smaller answer gives the right answer for n. If both hold, the function is correct by induction.

Quick check

Write a recursive sum of the digits of a non-negative integer n.

Remember

Base case first.
Every call must move towards the base case.
Trust the smaller call; verify only the base case and the combine step.

Common mistakes

Missing or unreachable base case (StackOverflowError).
Recursing on the same size (e.g. f(n) calling f(n)).

Words used in this lesson

Base case: An input answered directly, which stops the recursion.
Recursive case: The step that calls the function on a smaller input.
Induction: Proving something for n by assuming it for smaller sizes.

Command Palette

Thinking Recursively

1.The two parts

2.The leap of faith