## Slides

## 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)`

:

Iteration | seconds | nextCount |
---|---|---|

0 | ||

1 | ||

2 | ||

3 | ||

4 |

## 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

## Click Here for Solution

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

## 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)`

:

Iteration | n | (n - 1) | factorial(n - 1) | return value |
---|---|---|---|---|

0 | ||||

1 | ||||

2 | ||||

3 | ||||

4 |

## 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;
}
```

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.

## Links

- https://javascript.info/recursion
- https://www.youtube.com/watch?v=k7-N8R0-KY4
- http://2ality.com/2015/06/tail-call-optimization.html