Recursion

Problem

How many arrangements are there?

There are 5 books on the shelf. In how many ways can you arrange them? For the first spot there are 5 choices, for the second 4, then 3, 2 and 1: 5 · 4 · 3 · 2 · 1 = 120. This is a factorial, written 5!.

You can already do it with a loop:

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

console.log(factorialLoop(5));

Output

120

Look at it this way too: 5! = 5 · 4!. And 4! = 4 · 3!. The task is solved through the same task, only smaller. Can the function say exactly that?

The idea

A function that calls itself

It can. A function that calls itself is called recursive, and the approach is recursion.

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

console.log(factorial(5));

Output

120

Two things make it work:

• A base case. A case that is solved directly, without a new call. Here: 1! = 1.
• A smaller task. Each call calls itself with a number closer to the base case: n - 1.

See it

The pile of calls

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

console.log(factorial(3));  // 6

Step by step, in words

1. The program calls factorial(3).
2. New memory for factorial with n = 3.
3. 3 is not 1, so the function calls factorial(2) and waits for the answer.
4. The same again: factorial(2) calls factorial(1). Each call has its own n.
5. n is 1: this is the base case. It returns 1 without calling again.
6. The answer comes back down: 2 * 1 = 2.
7. And again: 3 * 2 = 6.
8. factorial(3) returns 6 and the program prints it.

Each call gets its own memory with its own n. They pile up one on top of the other and wait. This pile is called the call stack. When the base case returns 1, the answers go back down one by one and the pile comes apart.

Try it

Down and back up

What will the program print?

function steps(n) {
  if (n === 0) {
    return;
  }
  console.log(`down ${n}`);
  steps(n - 1);
  console.log(`up ${n}`);
}

steps(2);

Answer

down 2
down 1
up 1
up 2

down 2
down 1
up 2
up 1

down 2
up 2
down 1
up 1

Check

Try it

Find the bug

sumTo(4) should return 1 + 2 + 3 + 4 = 10. Instead, the program stops with RangeError: Maximum call stack size exceeded. Which line is the bug on?

Pick the line with the bug.

1function sumTo(n) {2 if (n === 1) {3 return 1;4 }5 return n + sumTo(n);6}

Check

The idea

Recursion or a loop?

You can write the factorial with a loop or with recursion. Here the loop is the better choice: it does not pile up memory for each call, and for 100,000 calls the stack will not be enough.

Recursion is natural where a thing contains smaller things of the same kind: a folder with folders inside, a category with subcategories, a branch with branches. You will come across tasks like these later in the course. There a loop gets clumsy, while the recursive function stays short.

More precisely, if you are curious

• The factorial is often written with the base case 0! = 1 (if (n === 0)). Then it works for 0 too.

• In JavaScript every number is a decimal (double), and big whole numbers are stored approximately. Up to 22! the result is exact, but 23! is already rounded. For exact whole numbers with no limit there is BigInt: a number with an n at the end (23n):

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

function factorialBig(n) {
  if (n === 1n) {
    return 1n;
  }
  return n * factorialBig(n - 1n);
}

console.log(factorial(23));
console.log(factorialBig(23n));

Output

2.585201673888498e+22
25852016738884976640000n

Try it

Put the lines in order

The function has to work out a power: power(2, 10) is 1024. Put its lines in order.

1. }↑↓
2. function power(base, exp) {↑↓
3. }↑↓
4. if (exp === 0) {↑↓
5. return base * power(base, exp - 1);↑↓
6. return 1;↑↓

Check

Exercise

Recursive tasks

1. Factorial two ways. Write factorialLoop(n) with a for loop and factorial(n) with recursion. Read a number and print the result from both functions.

Input

5

Output

The factorial of 5 is 120
The factorial of 5 is 120

2. Sum of digits. sumDigits(n): the last digit (n % 10) plus the sum of the digits of the rest (Math.trunc(n / 10)). The base case is a single-digit number.

3. Fibonacci. Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8… fib(n) returns the nth number. Try it with 10, and then with 45. Why is it so slow? Hint: how many times is each number worked out?

4. Palindrome. isPalindrome(s): the first and last letters are the same, and the middle is a palindrome. The base case is a word with 0 or 1 letters.

Calls

sumDigits(2024)
fib(10)
isPalindrome("level")
isPalindrome("ABCDE")

Output

8
55
true
false

Test

Check yourself

1. What is recursion?

Two functions with the same nameA loop inside a functionA function that calls itself

2. Why does a recursive function need a base case?

So it stops calling itselfSo it can return a resultSo it runs faster

3. factorial(3) calls factorial(2), and that calls factorial(1). How many variables n are in memory just before factorial(1) returns?

ThreeOneNone

4. What happens if the base case is never reached?

The function returns 0The program runs forever, with no errorThe stack overflows and the program stops with a RangeError

Check

Start the lesson over