Recursion

recursion is when a function calls itself

(like Ouroboros, a mythical serpent who eats its own tail)

(image source: wikipedia, public domain)

Infinite Recursion

Here's a not very useful recursive function:

function go() {
  console.log("Go!");
  go();                // do it all again
}

Call this function with go(), then either wait a few seconds, or stop it by pressing CTRL-C.

RangeError: Maximum call stack size exceeded means that go has called itself too many times.

Recursion Requires Termination

For recursion to be useful, it needs to (eventually) stop.

The standard way to stop is called a guard clause.

Also called a base case or a terminator.

function countdown(seconds) {
  if (seconds === 0) {
    console.log("Blastoff!");
  }

This means, "When seconds reaches 0, stop recursing."

Countdown

The simplest form of recursion uses a counter; in this example we are counting down the seconds until a rocket launches.

function countdown(seconds) {
  if (seconds == 0) {
    console.log("Blastoff!");
  } else {
    console.log("" + seconds + "...");
    let nextCount = seconds - 1;
    countdown(nextCount);
  }
}

countdown(10);

Put the above in a source file called countdown.js and try it now.

Note that you must change the value; otherwise you will recurse forever.

Exercise: Draw It Out

Please dive into the above countdown function in excruiciating detail.

Fill out the cells of the following table for the call countdown(5):

Recursion is Reduction

In addition to the base case, a recursive function needs to define at least one other case; this case wraps around the base case like a Russian doll.

You can think of a recursive function as starting with a large problem, and gradually reducing the problem until it reaches the base case.

Since the base case has a known solution, every other step can then be built back up on top of it -- which is why it's called the base.

In this way, recursion is an example of the divide and conquer approach to problem-solving.

(image source: wikipedia, public domain)

Lab: Recursive Factorial

To find the factorial of a number N, take all the counting numbers between 1 and N and multiply them together.

Write a recursive function called factorial that takes a number and returns its factorial.

Remember to start with the base case!

factorial(1)    // 1
factorial(2)    // 2
factorial(3)    // 6
factorial(10)   // 3628800

Solution: Factorial

Exercise: Draw It Out

Please dive into the above factorial function in excruciating detail.

Fill out the cells of the following table for the call factorial(5):

Recursion vs Loops

Recursion can be seen as another kind of loop, like for or while or reduce.

In fact, most recursive functions can be "unrolled" and rewritten using a loop and a stack.

For example, here is factorial using a stack instead of recursion:

function factorial(n) {
    let stack = [];
    while (n >= 1) {
        stack.push(n);
        n = n - 1;
    }
    let f = 1;
    while (stack.length > 0) {
        f = f * stack.pop();
    }
    return f;
}

console.log(factorial(5)) // => 120

What do you think about this implementation compared to the previous one? What are the advantages and disadvantages of recursion vs. loops?

Lab: Recursive Fibonacci

Using recursion, write a program called fib.js so that running node fib.js 10 prints

[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]

which are the first 10 elements of the Fibonacci sequence.

Recursive Fibonacci solution