What is recursion? Base case and recursive case

A recursive function is a function that calls itself. That sounds circular, but each call works on a smaller version of the problem, and the smallest versions are answered directly. It's how you'd explain a factorial in words: 4! is 4 times 3!, and 3! is 3 times 2!, and so on down to 1! = 1, which you just know.

factorial(4) asks for 4 times factorial(3), which asks for 3 times factorial(2), which asks for 2 times factorial(1). factorial(1) is the base case and returns 1 straight away. Then the answers flow back up: factorial(2) returns 2, factorial(3) returns 6 and factorial(4) returns 24.

The two parts of every recursive function

The base case — an input small enough to answer directly, with no further call. Here: factorial(1) is 1. Without a base case the calls never stop.
The recursive case — express the answer using the same function on a smaller input, then finish the job. Here: factorial(n) = n × factorial(n − 1). Each call must move closer to the base case.

Dry-run simulator

The call stack (factorial)

Each call waits for the one it made; the answers come back in reverse order.

The code

1function factorial(n) {2  if (n <= 1) return 1;            // base case: no more calls3  return n * factorial(n - 1);     // pauses here until the inner call returns4}5 6factorial(4);

JavaScript6 lines

Time O(n) — one call per number. Space O(n) — the calls wait on top of each other until the base case answers (the next lesson shows exactly where that memory goes).

How to write a recursive function

Say what the function returns for any input, in one sentence: "sumDigits(n) returns the sum of n's digits."
Find the base case: the smallest input you can answer outright. A single digit is its own sum.
Shrink the problem: how does the answer for n follow from the answer for something smaller? The digits of 1234 are the digits of 123, plus 4.
Trust the recursive call — the "leap of faith". Assume sumDigits(123) already works; don't trace it in your head. If the base case is right and every call gets smaller, it works.

1function sumDigits(n) {2  if (n < 10) return n;                          // one digit: it is its own sum3  return sumDigits(Math.floor(n / 10)) + (n % 10);   // the other digits, plus the last one4}

JavaScript4 lines

Why use recursion?

Every recursive function can be written as a loop, and loops are usually a little faster. But many problems are naturally recursive — trees, nested brackets, "try every way" searches, divide-and-conquer sorts — and the recursive code is shorter and closer to how you'd describe the solution. Backtracking, tree traversals, merge sort, quick sort and most dynamic programming start as recursion.

Common mistakes

No base case, or one that's never reached — factorial(-1) with a base case of n == 1 calls forever, until the program crashes with a stack overflow.
Not shrinking — calling f(n) from f(n) again, or shrinking by the wrong amount and jumping past the base case.
Forgetting to return — writing factorial(n - 1) without using its result.
Tracing every call in your head — for deep recursion it's hopeless. Check the base case and one step instead.

Key takeaways

Recursion = a base case answered directly + a recursive case that uses the same function on a smaller input.
Each call waits for the call it made; answers come back in reverse order.
Write it by stating what the function returns, then trusting the smaller call.
It's the foundation of backtracking, tree algorithms and dynamic programming.

Was this helpful?