Recursion Explained (with Examples)
Tags: recursion, javascript, beginners, webdev
Published: 2020-07-08 00:12:15

> “To understand recursion, one must first understand recursion” - Unknown

**Recursion** is a method of solving problems where you solve smaller portions of the problem until you solve the original, larger problem. A method or function is recursive if it can call itself. 

```javascript
function understandRecursion(doIUnderstandRecursion) {
	const recursionAnswer = confirm('Do you understand recursion?');
	if(recursionAnswer === true) { // base case
		return true;
	}
	understandRecursion(recursionAnswer); // recursive call
}
```
For the example above, notice the base case and recursive call which make this a recursive algorithm. Recursive functions must have a **base case**, or a condition in which no recursive call is made. I think the best way to understand recursion is to look at examples so let’s walk through two common recursive problems. 


## Example 1: Calculating the Factorial of a Number
Calculating the factorial of a number is a common problem that can be solved recursively. As a reminder, a factorial of a number, n, is defined by n! and is the result of multiplying the numbers 1 to n. So, `5!` is equal to `5*4*3*2*1`, resulting in `120`. 

Let’s first take a look at an iterative solution:
```javascript
function factorial(num) {
	let total = 1;
	for(let n = num; n > 1; n--) {
		total *= n;
	}
	return total;
}
```

The iterative solution above is fine but let’s try rewriting it using recursion. When we think about solving this problem recursively, we need to figure out what our subproblems will be. Let’s break it down:
1. We know `factorial(5) = 5 * factorial(4)` aka `5! = 5 * 4!`.
2. To continue, `factorial(5) = 5 * (4 * factorial(3))` which equals `5 * (4 * (3 * factorial(2))` and so on…
3. ...Until you get `5 * 4 * 3 * 2 * 1` and the only remaining subproblem is `1!`. 
4. `factorial(1)` and `factorial(0)` always equals 1 so this will be our base case.

Using this line of thinking, we can write a recursive solution to our factorial problem:
```javascript
function factorial(n) {
	if(n === 1 || n === 0) { // base case
		return 1;
	}
	return n * factorial(n - 1); // recursive call
}
```

## Example 2: Fibonacci Sequence
Another fun problem that can be solved using recursion is the Fibonacci sequence problem. As a reminder, the Fibonacci sequence is a series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The pattern involves totaling the two previous numbers so 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, etc.  In other words, the Fibonacci number at position `n` (for `n > 2`) is the Fibonacci of `(n - 1)` plus the Fibonacci of `(n - 2)`.

Again, I think it’s helpful to see an iterative solution first:
```javascript
function fibonacci(n) {
    if(n === 0) return 0;
	if(n === 1) return 1;

	let fibNMinus2 = 0;
	let finNMinus1 = 1;
	let fibN = n;

	for(let i = 2; i <= n; i++) { // n >= 2
		fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
		fibNMinus2 = fibNMinus1;
		fibNMinus1 = fibN;
	}
	return fibN;
}
```

As you’ll see, the recursive solution looks much simpler:
```javascript
function fibonacci(n) {
	if(n === 0) return 0; // base case 1
    if(n === 1) return 1; // base case 2

	return fibonacci(n - 1) + fibonacci(n - 2); // recursive call
}
```
If you were to call fibonacci(5), the following represents the calls that would be made:
![anatomy of recursive solution to Fibonacci problem](https://www.andreagrandi.it/images/2015/08/fibo.png)

### Fibonacci with Memoization
I wanted to take this opportunity to mention another approach to this problem, called memoization. **Memoization** consists of an optimization technique that stores the values of the previous results, similar to a cache, making our recursive solution faster. If you look back at the calls made to compute `fibonacci(5)` in the image above, you can see that `fibonacci(3)` was computed twice, so we can store its result so that when we compute it again, we already have it. 

Take a look at how our `fibonacci` solution changes when we add memoization:
```javascript
function fibonacci(n) {
	const memo = [0, 1]; // cache all computed results here
	const fib = (n) => {
		if(memo[n] != null) return memo[n]; // base case
		return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // recursive call
	};
        return fib(n);
}
```
## Why Use Recursion?
To be completely frank, a recursive solution is almost always slower than an iterative one. That being said, if you look back at our Fibonacci solutions, the recursive solution is much easier to read plus memoization can help bridge the gap in speed. Recursion is generally easier to understand and usually requires less code. 

## Conclusion
Now that we’ve gone over some examples, I hope recursion is a little easier for you to grasp and that you can see why we would use it. In a future post, I plan to take a look at the [tree data structure](https://dev.to/christinamcmahon/understanding-binary-search-trees-4d90) which uses recursion in many of its methods so stay tuned! This article only scratches the surface of recursion’s potential so here are a few resources you might find helpful if you want to continue your studies.
- [Practice with Recursive Problems](https://www.hackerrank.com/domains/algorithms?filters%5Bsubdomains%5D%5B%5D=recursion) via HackerRank
- [Famous Recursive Problems](https://introcs.cs.princeton.edu/java/23recursion/) via Princeton