Recursion Basics

A function that calls itself

You are standing in a long queue (a line of people) and want to know your position. You cannot see the front. So you ask the person in front of you: “What is your position?” They do not know either, so they ask the person in front of them, and so on. The person at the very front knows the answer without asking: “1”. Each answer then travels back: 2, 3, 4… until it reaches you.

That is recursion. Recursion is a way of solving a problem by asking the same question about a smaller version of the problem. In code, it is a function that calls itself. (A function is a named block of code that you can run by calling its name.) The example below counts down from 3. Each call prints one number and then calls the same function with a smaller number.

function countdown(n) {  if (n === 0) {                // base case: stop here    console.log("Lift-off!");    return;  }  console.log(n);  countdown(n - 1);             // recursive case: a smaller problem}countdown(3);// 3// 2// 1// Lift-off!

Base case and recursive case

Every correct recursive function has these three parts:

The hardest part for beginners is trusting the recursive call. Take the factorial as an example. The factorial of n, written n!, is n × (n − 1) × … × 1. So 4! = 4 × 3 × 2 × 1 = 24. When you write factorial(n - 1), do not try to follow it all the way down. Assume it returns the correct answer for n − 1. Then ask only: how do I use that to get the answer for n? Since n! = n × (n − 1)!, the answer is n * factorial(n - 1).

Traced: factorial(4) and the call stack

Now let us follow it all the way down once, to see what the computer really does. Watch the stack variable. It shows every call that has started but has not finished yet.

▶function factorial(n) {2  if (n === 1) return 1;3  return n * factorial(n - 1);4}5console.log(factorial(4));

The call stack, drawn

The call stack is the list of function calls that are still running. A stack is a list where you add and remove items only at the top, like a pile of plates. Each call gets its own frame. A frame is the note the computer keeps for one call: its own copy of n and the place where the call must continue. New frames go on top. Only the top frame runs. When it returns, it is removed and the frame below continues.

This is why recursion has a space cost. Lesson 12 said that space complexity counts the extra memory a program uses. The call stack is extra memory. So factorial(n) uses O(n) space.

Printing 1 to N and N to 1

Where you put the work decides the order. You can put it before the recursive call or after it. Work done before the call happens on the way down. Work done after the call happens on the way back up.

function upTo(n) {  if (n === 0) return;  upTo(n - 1);          // first handle 1 … n-1  console.log(n);       // then print n  → printed on the way back}function downFrom(n) {  if (n === 0) return;  console.log(n);       // print n first → printed on the way in  downFrom(n - 1);}upTo(3);    // 1 2 3downFrom(3); // 3 2 1

Sum and factorial

Many maths definitions are already recursive. Write the definition, translate each line into code, and the function is finished:

// sum(n) = n + sum(n - 1),   sum(0) = 0function sumTo(n) {  if (n === 0) return 0;  return n + sumTo(n - 1);}// n! = n × (n - 1)!,   0! = 1function factorial(n) {  if (n <= 1) return 1;  return n * factorial(n - 1);}console.log(sumTo(5));      // 15console.log(factorial(5));  // 120console.log(factorial(0));  // 1

Note the base case n <= 1 in this factorial. It also covers 0! = 1 (by definition, the factorial of 0 is 1). If the base case were only n === 1, then factorial(0) would call factorial(-1), then factorial(-2), and never stop. (The earlier traced version only works for n ≥ 1.)

Recursion on arrays and strings

For an array or string, “a smaller problem” usually means “the same thing without its first item”. You can pass an index that moves forward, or you can pass a shorter copy:

// The sum of an array = first item + the sum of the restfunction sumArray(arr, i = 0) {  if (i === arr.length) return 0;          // nothing left  return arr[i] + sumArray(arr, i + 1);}// A string reversed = (the rest reversed) + the first characterfunction reverse(s) {  if (s.length <= 1) return s;  return reverse(s.slice(1)) + s[0];}console.log(sumArray([4, 1, 7]));  // 12console.log(reverse("code"));      // edoc

Passing an index is cheaper. s.slice(1) makes a copy of the string (everything except the first character) on every call. That adds an O(n) step to each of the n calls, so the total is O(n²). For short inputs either way is fine. In interviews, prefer the index.

Two calls at once: Fibonacci

The Fibonacci numbers are a list of numbers where each one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13… The definition translates directly into code with two recursive calls:

function fib(n) {  if (n < 2) return n;                 // fib(0) = 0, fib(1) = 1  return fib(n - 1) + fib(n - 2);      // two recursive calls}console.log(fib(10)); // 55

It is correct, but look at how many calls it makes. fib(5) calls fib(4) and fib(3). Then fib(4) calls fib(3) again. The same values are worked out over and over:

A loop that remembers the last two values does the same job in O(n). Lesson 32 draws these calls as a tree. Lesson 54 fixes the repetition with memoisation. Memoisation means saving the answer of a call the first time you work it out, so that you can reuse it instead of calculating it again. It is the first step into dynamic programming (solving a big problem by saving the answers to its small problems).

Stack overflow

Every frame uses memory, and the call stack has a size limit. Suppose there is no base case, or the base case is never reached. Then the stack fills up. This is called a stack overflow, and JavaScript stops the program with an error:

function forever(n) {  return forever(n + 1);   // no base case}forever(0);// RangeError: Maximum call stack size exceeded

In Node.js the limit is roughly 10,000 frames for a simple function. The exact number depends on the engine and on how much each frame stores. So even a correct recursion fails if it goes too deep. sumTo(100000) overflows, while a loop handles it easily.

Recursion or a loop?

Anything written with recursion can be written with a loop, and the other way round. Choose the one that is easier to read:

For the simple problems in this lesson, loops are usually better in practice. We use recursion here because the problems are small enough to follow every step. You will need the same skill for trees (Part 11), backtracking (Part 8) and dynamic programming (Part 14), where recursion is the natural tool. (Backtracking means trying a choice, and going back to undo it if it does not work.)

Practice questions

For each question, write the base case first, then the recursive case. Then dry-run the smallest input that is not the base case. (To dry-run means to follow the code by hand, line by line, with a small input.)

function sumDigits(n) {  if (n < 10) return n;  return (n % 10) + sumDigits(Math.floor(n / 10));}console.log(sumDigits(472)); // 13console.log(sumDigits(5));   // 5

function sumDigits(n) {  let sum = 0;  while (n > 0) {    sum += n % 10;    n = Math.floor(n / 10);  }  return sum;}console.log(sumDigits(472)); // 13

function isPowerOfTwo(n) {  if (n === 1) return true;  if (n <= 0 || n % 2 !== 0) return false;  return isPowerOfTwo(n / 2);}console.log(isPowerOfTwo(16)); // trueconsole.log(isPowerOfTwo(1));  // trueconsole.log(isPowerOfTwo(6));  // falseconsole.log(isPowerOfTwo(0));  // false

function isPowerOfTwo(n) {  if (n <= 0) return false;  while (n % 2 === 0) n /= 2;  return n === 1;}console.log(isPowerOfTwo(16)); // trueconsole.log(isPowerOfTwo(6));  // false

function reverseString(s, left = 0, right = s.length - 1) {  if (left >= right) return;               // 0 or 1 characters left  [s[left], s[right]] = [s[right], s[left]];  reverseString(s, left + 1, right - 1);}const s = ["h", "e", "l", "l", "o"];reverseString(s);console.log(s); // [ 'o', 'l', 'l', 'e', 'h' ]

function reverseString(s) {  let left = 0, right = s.length - 1;  while (left < right) {    [s[left], s[right]] = [s[right], s[left]];    left++;    right--;  }}const s = ["h", "e", "l", "l", "o"];reverseString(s);console.log(s); // [ 'o', 'l', 'l', 'e', 'h' ]

function isPalindrome(s, i = 0, j = s.length - 1) {  if (i >= j) return true;  if (s[i] !== s[j]) return false;  return isPalindrome(s, i + 1, j - 1);}console.log(isPalindrome("racecar")); // trueconsole.log(isPalindrome("abca"));    // falseconsole.log(isPalindrome(""));        // true

function fib(n) {  if (n < 2) return n;  return fib(n - 1) + fib(n - 2);}console.log(fib(2));  // 1console.log(fib(10)); // 55

function fib(n) {  let a = 0, b = 1;               // fib(0), fib(1)  for (let i = 0; i < n; i++) {    [a, b] = [b, a + b];  }  return a;}console.log(fib(2));  // 1console.log(fib(10)); // 55console.log(fib(50)); // 12586269025

function isSorted(arr, i = 0) {  if (i >= arr.length - 1) return true;     // 0 or 1 items left  if (arr[i] > arr[i + 1]) return false;  return isSorted(arr, i + 1);}console.log(isSorted([1, 2, 2, 5])); // trueconsole.log(isSorted([3, 1, 4]));    // falseconsole.log(isSorted([]));           // true

function countOf(arr, x, i = 0) {  if (i === arr.length) return 0;  return (arr[i] === x ? 1 : 0) + countOf(arr, x, i + 1);}console.log(countOf([3, 1, 3, 3, 2], 3)); // 3console.log(countOf([], 7));              // 0

function countOf(arr, x, i = 0, count = 0) {  if (i === arr.length) return count;  return countOf(arr, x, i + 1, count + (arr[i] === x ? 1 : 0));}console.log(countOf([3, 1, 3, 3, 2], 3)); // 3

Make it stick

What's next

Lesson 15 closes Part 2 with hashing. You will count with arrays and Maps and answer frequency questions. Then you will look inside a hash table to see why map.get takes about the same time for ten items as for ten million.