Previously we looked at loops, which enabled us to repeat a block of code under some limits. We also discovered types of loops that can run forever if we aren’t careful.
Recursion can do everything that loops can do, and more. Some people find recursion trickier to think about than loops. But some find it makes more sense.
While recursion isn’t used too often in professional Javascript, it is a very common programming tool in general. And since this is a programming course, rather than a Javascript specifics course, I think it is important to learn.
Recursion simply means “self reference”. In programming, it refers to a function that calls itself. I’ll start with a basic example, then show you how to design recursive functions.
function countdown(i) {
console.log(i);
if (i == 0) {
return;
}
countdown(i-1);
}
Here’s a function, countdown, that counts down from some number.
The function logs a number, and then continues counting down from
a smaller number. If you run this code (go ahead and try it), you’ll
see that it does indeed countdown. No loops!
Sometimes recursion can be a simpler way of expressing a solution. Instead of talking about how to calculate something, a recursive definition looks more like declaring what something is. We’ll see this more in a bit.
In general, our function needs two things:
In the countdown example, it will call itself only if it has not already reached zero.
A classic demonstration of recursion is via the Fibonacci sequence. This is a series of numbers that goes 1, 1, 2, 3, 5, 8, 13, etc. The first two values are 1, and each number after that is the sum of the two numbers before hand. This was originally created to represent the number of rabbits after some number of generations.
Let’s build a function to compute the nth entry in the Fibonacci sequence.
// Lets say the first entry is fib(1)
function fib(n) {
if (n < 3) {
return 1;
}
return fib(n-1) + fib(n-2);
}
If n < 2, then the entry is 1. Otherwise, it is the sum of the two terms before it. See how our code parallels the description of the problem?
The function above computes the right value, but does so after repeating a lot of work. To see this, lets see what it would look like to calculate fib(5).
fib(5) = 5
|--> fib (4) = 3
| |--> fib(3) = 2
| | |--> fib(2) = 1
| | \--> fib(1) = 1
| \--> fib(2) = 1
|--> fib (3) = 2
|--> fib(2) = 1
\--> fib(1) = 1
Notice it each call needs to recompute earlier terms. Lets look at how many times a fib call needs to call itself, based on the value of n.
| n | total number of fib calls |
|---|---|
| 1 | 0 (base case) |
| 2 | 0 (base case) |
| 3 | 2 |
| 4 | 4 |
| 5 | 8 |
This grows quickly, almost like the fibonacci sequence itself! The issue is that each later call requires as many calls as the two just before it combined. If you tried to run fib(40), you would be waiting a while.
Lets try a new approach. We want to also pass along the values we computed previously, so it doesnt need to redo work.
// a and b will represent the two
// previously computed entries.
function fib2(entries_remaining, a, b) {
if (entries_remaining == 1) {
return b;
}
// This final parameter holds the next entry.
// We slide b into the old slot, so we continually
// keep a little "window" of the previous 2 values only.
return fib2(entries_remaining -1, b, b + a);
}
// lets hide faster version of fib behind a function
// that is as easy to use as our initial version.
function fib(i) {
return fib2(i, 0, 1);
}
Our new fib(40) completes instantly. While we’re still computing the same value, the way we do so is more efficient. Our new algorithm, or approach for computing fibonacci terms, is more efficient.
If you found this interesting, a future course will focus on solving problems, and developing increasingly efficient solutions.
While recursion can be a powerful technique for solving problems, you should know that not all programming languages support recursion efficiently.
Remember how, when a function is called, the program needs to remember where it came from? This is how it is able to jump back after it finishes. Every time you call a function, we need to remember where we came from. After returning, that location can be forgotten.
This means that deeply nested recursive calls can consume increasing amounts of space (memory).
The solution to this is something called Tail-Call optimization (aka TCO). If the very last thing the function does is call itself, the program does not technically need to remember another position. It can just replace the old position it was remembering. This limits the extra space required for running recursive functions.
Our fib2 is tail recursive, so lets use that as an example. Here’s what fib(5) looks like now:
fib(5)
\->fib2(5, 0, 1)
fib2(4, 1, 1)
fib2(3, 2, 2)
fib2(2, 3, 3)
fib2(1, 5, 5) = 5
Since fib2(1, 5, 8) is just going to return right away, the program doesn’t need to keep track of that list. If your programming language supports Tail-call optimization, when fib2 runs it instead stores something like this:
fib(5)
\->fib2(5, 0, 1)
fib2(1, 5, 8) = 5
If you are working with deeply nested recursive functions, you should double check that your programming language and environment support TCO. Javascript does, but each browser has their own Javascript implementation. Not all browsers support TCO.
| n | fib(n) |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
Which version do you think is easier to write? Which one do you think is easier to read?
| n | tri(n) |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 6 |
| 4 | 10 |
| 5 | 15 |
Implement a function tri(n). Do it once using loops, and once using recursion.
Show / Hidefunction fib(entries_remaining) {
let a = 0;
let b = 1;
while (entries_remaining > 1) {
let c = a + b;
a = b;
b = c;
entries_remaining -= 1;
}
return b;
}
// recursive implementation
function tri(n) {
if (n == 1) {
return 1;
}
return n + tri(n - 1);
}
// loop implementation
function tri(n) {
let sum = 0;
while (n > 0) {
sum += n;
n -= 1;
}
return sum;
}
So far we’ve been looking at ways of combining basic building blocks for code. Next we’ll look at a few ways of combining data, which will expand the reach of things we can represent nicely within our programs. First we’ll look at arrays.