# Recursion

## Learning Goals

- Understand the concept of recursion
- Understand the limitations of recursion in JS & Ruby
- Be able to solve problems using recursion
- Know the theory behind Tail Call Optimization

## Prework

- Read this article - 6 minutes
- Read this article - 6 minutes
- Watch this video - 12 minutes

## Discussion on Prework

Reflecting on the prework, discuss the following questions with a peer:

- Describe what recursion is? How does it compare to loops?
- What are some scenarios that recursion is best for?
- What performance issues does recursion have in languages like JavaScript & Ruby?

## Reviewing Key Concepts

Recursion is an important programming technique in which **a function CALLS ITSELF**. Yes, you read that right.

More specifically, a recursive function is a function that calls itself *until* it arrives at a final result.

## The anatomy of a recursive function

Every recursive function (reminder, just a function that calls itself) must have these two pieces:

- A simple
**base case**(or cases): a terminating scenario that*does not use recursion*to produce an answer- Often written as an
`if`

statement - Think of this as similar to the test condition in a for loop - under what condition do we want to STOP recursively calling the function?
- Without a base case (like a loop without a valid test condition) we will end up recursively calling the function FOREVER… or until we get a stack overflow error.

- Often written as an
- A
**recursive case**: A set of instructions, moving closer towards the base case, that ends in a call to the same function

Let’s see this in action with a function that takes a number as an argument and counts down to zero.

**Javascript Prompt**

```
countdown( 3 );
// We want this function to countdown from the starting number until we get to 0
// 3
// 2
// 1
// 0
```

**Psuedocode**

```
const countdown = number => {
//base case - when do we want to stop?
//stop when we get to zero (0)
//recursive case
//print the number we are currently on
//call the countdown function again with the next number
}
```

**Solution**

```
const countdown = number => {
// check our base case, if statement
if (!number) {
return 0;
}
console.log(number);
// recursive case moving towards base case
return countdown(number - 1)
}
countdown(3); // 3, 2, 1, 0
```

**Ruby Prompt**

```
countdown(3)
# We want this function to countdown from the starting number until we get to 0
# 3
# 2
# 1
# 0
```

**Psuedocode**

```
def countdown(num)
# base case - when do we want to stop?
# stop when we get to zero (0)
# recursive case
# print the number we are currently on
# call the countdown function again with the next number
end
```

**Solution**

```
def countdown(num)
# check our base case, if statement
if num < 0
return
end
p num
# recursive case moving towards base case
countdown(num - 1)
end
```

### Advantages

- Allows you to break problems down into the smallest, most repeatable step and do that small step over and over!
- Useful for iterative branching including:
- fractal math
- sorting
- traversing nodes of complex/non-linear structures (binary or prefix tries)

- Recursion is more functional in that it doesn’t keep track of state (no side effects)

### Disadvantages

- Recursion is not optimized in many languages including JS & Ruby
- Execution contexts continue to get built on the callstack.
- With bigger datasets, this can be a problem.
- Memory consumption can lead to the
`maximum call stack size being exceeded`

. - Loops on the otherhand don’t need to add functions to the call stack. (better memory management)

- Memory consumption can lead to the

## Diving Deeper Into The Process

Let’s work through one more together and write out a function that takes in an argument of an array of numbers and adds them together.

**Javascript Setup**

```
let numbers = [ 1, 2, 3, 4 ];
getSum(numbers); // 10
```

**Ruby Setup**

```
numbers = [1,2,3,4]
get_sum(numbers)
# => 10
```

</details>

One of the most basic patterns of recursion is when you can reduce a problem to a smaller one and then keep reducing until you can’t do it anymore. This is also known as natural recursion.

So, at the most basic level, we just want to add one number with another number! How might this look in psuedocode? (Try it on your own first, then check out the pseudocode below.)

### Psuedocode

```
//base case
//if there are no more numbers to add, return 0
//recursive case
//take the first number from the nums array
//add that number to the result of calling getSum with the remaining numbers
```

It can be helpful to break down what each step of this problem looks like. Here’s one way to visualize the call stack:

### Solution

**Javascript Solution**

```
const getSum = nums => {
// base case
if (!nums.length) {
return 0;
}
// get closer to base case
let firstNumber = nums.shift();
return firstNumber + getSum(nums);
}
```

**Ruby Solution****

```
def get_sum(nums)
# base case
if nums.empty?
return 0
end
# get closer to base case
first_number = nums.shift
first_number + get_sum(nums)
end
```

## Exercises

The best way to start understanding recursion is to just try doing it! Feel free to work through these problems in either JavaScript or Ruby.

### Exercise 1

**Factorial**

In mathematics, the factorial of a non-negative integer is the product of all positive integers less than or equal to n. For example, the factorial of 5 is 120.

```
5 x 4 x 3 x 2 x 1 = 120
```

Write a recursive function that calculates the factorial of a number.

### Exercise 2

**Reverse a string.**

```
// create a function which takes a string of characters and
// recursively calls itself to reverse the string
// e.g.
let reversedString = reverse('Ariel')
console.log(reversedString); // leirA
```

### Exercise 3

**Calculate a number to a specific power.**

```
// create a function which takes a number and an exponent and
// recursively calls itself to calculate the product
// e.g.
let base = 2;
let exponent = 4;
let product = power(base, exponent) // 2 to the 4th power
console.log(product); // 16
```

### Exercise 4

**Palindrome Checker**

A palindrome is word/number that reads the same forwards and backwards. Examples include `racecar`

, `tacocat`

, and `toot`

.

Write a recursive function that determines whether a given input is a palindrome!

**Hint:** An empty string AND a letter would technically be considered palindromes in this example.

```
// create a function which takes a string
// and recursively calls itself to determine if the string is palindrome
// e.g.
console.log(isPalindrome('racecar')); // true
console.log(isPalindrome('a')); //true
console.log(isPalindrome('library')); // false
console.log(isPalindrome('dngojkafnghkoasng')); // false
```

### Tail Call Optimization

Great work on writing some recursive functions! As you read earlier, recursion isn’t really optimized for JS or Ruby. By adding to the call stack with each recursive call, this can become too much to handle for recursive functions using large datasets! To get around the stack overflow issue, one can use *tail call optimization*. A tail call refers to the last action that is **executed**. In this scenario, the recursive call must be the *last statement* of the recursive function.

Let’s think back to our `getSum`

function we wrote earlier…

```
// Example:
// Create a getSum fn that adds all of the numbers in an array
// Example that is not optimized due to it returning an operation
return firstNumber + getSum(nums);
// Example suited for tail call optimization
return getSum(nums, sum + firstNumber);
```

Notice with the first example, we are returning an operation. In this scenario, this would need to be added to the callstack because this cannot be executed until we know what `getSum(allNumbers)`

returns.

In the second example, we are only returning the recursive function and passing what arguments we need to keep track of the sum, making this perfect for Tail Call Optimization so that it can execute immediately instead of stacking in memory. Taking what we understand from this, let’s make some adjustments to the solution we just worked through!

### Tail Call Optimization Solution for `getSum`

```
const getSum = (nums, sum=0) => {
// base case
if (!nums.length) {
return sum;
}
// get closer to base case
let firstNumber = nums.shift();
return getSum(nums, sum + firstNumber);
}
```

Note that for Javascript, this optimization is only available in Safari. (Chrome, FireFox, and other browsers are not optimized currently). Read here to understand more of the history about this.

In Ruby, this optimization is not available by default. You *can* configure the Ruby compiler to enable tail call optimization however. If you’re interested, follow the article here!

### Bonus

Now try and solve these problems with tail call optimization!