## Slides

## Recursion

*recursion* is when a function *calls itself*

(like this pair of hands drawing themselves)

## Infinite Recursion

Here's a not very useful recursive function:

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

To stop this function, press CTRL-C.

## 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!"); } }

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

## 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 when recursing, you *must change* the value of the counter, else 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 |

## Lab: Recursive Factorial

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

Write a 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

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 excruiciating 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.