Recursion: when a function calls itself — Programming fundamentals

Video may be blocked due to browser extensions. In the article you will find a solution to this problem.

Lesson notes
Recommended watching
Optional reading
Optional watching
Lesson transcript

Lesson notes

Thinking about functions

You can think of functions as black boxes: a box takes a thing, does something, then spits some other thing out
- Some functions don't take anything (don't accept arguments), some don't do anything (their bodies are empty), some don't return any values.
- Our surfaceAreaCalculator takes one argument (radius), calculates the surface area and returns the result of that calculation.
Functions can call other functions
surfaceAreaCalculator can call the square function to get radius squared instead of manually multiplying radius by radius
We create functions to make our lives easier:
- the code is easier to understand
- functions can be reused many times

const surfaceOfMars = surfaceAreaCalculator(3390);  // this is WHAT, it's easier to understand
const surfaceOfMars = 4 * 3.14 * 3390 * 3390;       // this is HOW

Two functions together:

const surfaceAreaCalculator = (radius) => {
  return 4 * 3.14 * square(radius);
}

const square = (num) => {
  return num * num;
}

Functions calling themselves

Functions can call themselves
- Function definitions are descriptions of the boxes
- A real box is created when function is called
- If a function calls itself, a new identical box is created
Number of ways to arrange n objects is n! (permutations)
n! is defined like so: if n = 1, then n! = 1; if n > 0, then n! = n * (n-1)!

const factorial = (n) => {
  if (n === 1) {
    return 1;
  }
  else {
    return n * factorial(n-1);
  }
}

const answer = factorial(3);

Recursion requirements

A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.
A rule to move along the recursion, to go deeper. In our case, it was n * factorial(n-1).

Waiting for the multiplications

Nothing gets multiplied until we go all the way down, to the base case of factorial(1). Then we start going back up, one step at a time.

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1;
3 * 2;
6;

Sidenote

Note that 0! is 1, and the proper base case for n! is 0! In this lesson we omitted this case to make one less call and one less box to think about, since 1 * 1 is 1 anyway.

Just for fun

There is a common joke among programmers: "In order to understand recursion, you have to understand recursion". Google seems to love this kind of joke. Try googling "recursion" and check out the suggestion at the top of the results page ;-)
In order to understand recursion you must first understand recursion.

Recommended watching

What on Earth is Recursion? - Computerphile
Recursion (Part 7 of Functional Programming in JavaScript) from Fun Fun Function

Optional reading

Properties of recursive algorithms

Optional watching

Fibonacci Programming - Computerphile

Lesson transcript

We have a function surfaceAreaCalculator that accepts one argument — a radius — and returns a surface area of a corresponding sphere using a formula 4 * pi * r^2. Remember, we can think about functions as boxes: put a thing in the box, the box does something and spits out the result.

Some boxes don't accept anything, some — don't spit out anything, and some don't even do anything, but for now we're interested in boxes like surfaceAreaCalculator — accept something, calculate something, return the result.

We built this function in order to simplify our work. We have to calculate surface areas of different planets, and having this handy function means we don't have to remember and write down the formula over and over again.

Another reason is that now code is easier to understand. Compare this:

const surfaceOfMars = surfaceAreaCalculator(3390);

to this:

const surfaceOfMars = 4 * 3.14 * 3390 * 3390;

First one is much nicer and simpler, especially to someone who is new to this code. First one answers the "what" question, the second one answers the "how" question.

We can improve on this and make another function to calculate squares. Let's first take a look at how we might use it:

const surfaceAreaCalculator = (radius) => {
  return 4 * 3.14 * square(radius);
}

Instead of multiplying radius by radius, we call a square function and pass the radius. Obviously, the square function is nothing but "accept a number, return its square":

const square = (num) => {
  return num * num;
}

Let's trace the steps and see what happens when we run our program. We create a constant surfaceOfMars and tell it to store whatever value surfaceAreaCalculator function returns when it's called with 3390 as an argument.

3390 is known as radius inside the function. The function wants to multiply numbers and return, but it needs to know the last number, it has to call the square function and pass it the radius. square accepts one argument — it's the number 3390, in this case, and inside the square function it is known as n.

square wants to multiply n by n and return. Nothing stops it, so it does. We are back inside the surfaceAreaCalculator — it was literally waiting for the square function to finish. And now we have the result of calling square. It substitutes the call, so now it's possible to finish the multiplication and return.

The answer is returned and stored in the surfaceOfMars.

So, functions can call other functions. And a function doesn't know and doesn't care if it was called from inside another function. Maybe it was called from inside a function from inside another function from inside yet another function! It doesn't really matter as long as the computation comes back and finishes.

Let's try something else with functions calling functions. Say, you have three books on your shelf, and you want to know how many different ways to arrange them exists.

It turns out there are six ways to arrange 3 books. Four books — 24 ways. 13 books — almost as many ways as people on the planet. 25 books? More ways to arrange them than atoms in the universe.

In general, there are n! ways to arrange n books. Factorial means multiply all the numbers from 1 to n. So, 3! is 1 * 2 * 3. Let's write a factorial function:

const factorial = (n) => {
  return 1 * 2 * 3 * 4; // oh...
}

Oh wait. We don't know what n is, that's the point. Hmm... How do they do it in math?

Oh, okay, so, they have two options: if n is 1, then factorial is 1, this is simple. But if n is not 1, then factorial is n * (n-1)!

Let's try this:

const factorial = (n) => {
  if (n === 1) {
    return 1;
  }
  else {
    return n * factorial(n-1);
  }
}

const answer = factorial(3);

This might seem weird. We are calling a function from this function, but... it's the same function!

Is there something wrong? No, not really! The thing is, a function itself is not a box, it's a description of the box. When you call a function a box is created, and after it's done working it's destroyed. So, if you call the same function from itself, there's just another box created.

Let's trace it: we call factorial(3). 3 is not 1, so first condition is ignored. The function wants to multiply numbers and return the answer, but it can't — it needs to know the second number, so it calls factorial(3-1) or factorial(2).

A new identical factorial box is created, it accepts number 2, it's not 1, so it tries to multiply and return, but it can't — it needs to know the second number, so it calls factorial(1).

A new identical factorial box is created, it accepts number 1, and this box can return immediately — it returns 1.

1 comes back to the previous box, gets multiplied by 2 and the answer — 2 returns to the previous box, gets multiplied by 3 and the answer — 6 returns to the outside world and stored in the answer constant.

Phew!

This is called recursion: when something is described in terms of itself. When it comes to math or programming, recursion requires two things:

A simple base case or a terminating scenario. When to stop, basically. In our example it was 1: we stop factorial calculation when we get to 1.
A rule to move along the recursion, to go deeper. In our case, that was n * factorial(n-1).

Let's trace the steps once more, but from a different point of view. This is what happens step by step:

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1;
3 * 2;
6;

Nothing gets multiplied until we go all the way down, to the base case of factorial(1). And then we start going back up, one step at a time, one multiplication at a time.

Recursion is used widely, especially in functional programming — one of the styles of programming. And not only for math calculations, for all sorts of things! You'll see recursion all the time in this course and next ones, because it's extremely powerful and, I have to say, it's really cool.

It's your turn. Continue to the quiz and the exercise, and create your own recursive function. It might be a bit tricky, just remember: you need to describe two things — when to stop and how to go deeper. Good luck!