Photo by Taras Chernus on Unsplash

All About Recursion

Part 1 — Basics of Recursion

Recursion in computer science is the process in which the solution to a problem is based on the solutions to smaller instances of itself. In practice this consists of a function calling itself during the course of its execution.

In theory it’s a very simple and elegant concept but defining a recursive process can be difficult in practice. So let’s start simple. Finding the nth Fibonacci number is a classic problem that can be defined recursively.

The Fibonacci sequence is a series of numbers in which each subsequent number is the sum of the previous two numbers:

1st fibonacci num : 1 
2nd fibonacci num : 1 
3rd fibonacci num : 2 // 1 + 1 = 2
4th fibonacci num : 3 // 1 + 2 = 3
5th fibonacci num : 5 // 2 + 3 = 5
6th fibonacci num : 8 // 3 + 5 = 8
.
.
.
nth fibonacci num : (fibonacci num (n - 2) + fibonacci num (n - 1))

(Note: The first two Fibonacci numbers are always 1. This is important as this forms something called a base case or the most basic unit of truth in which you do not need to calculate something else in order to determine its value, an idea central to recursion; more on this later)

A basic pattern for the Fibonacci sequence arises; the nth Fibonacci number is simply

fib(n) = fib(n - 1) + fib(n - 2)

So if we were to calculate fib(6) then it’s simply fib(6 — 1) + fib(6 — 2) which is fib(5) + fib(4) which, if we consult the sequence above, is 5 + 3 which gives us 8 . Pretty cool huh?

But wait, what if we don’t know what fib(5) or fib(4) is? Great question. And herein lies the heart of recursion; we can use the same

fib(n) = fib(n — 1) + fib(n — 2)to calculate fib(5) and fib(4) .

So if we plug and chug we get the following:

fib(5) = fib(5 — 1) + fib(5 — 2) → fib(4) + fib(3)

fib(4) = fib(4 — 1) + fib(4 — 2) → fib(3) + fib(2)

Perfect, now we know how to calculate the 5th Fibonacci number! We simply add the 4th Fibonacci number to the 3rd! Wait…but we don’t know what the 4th and 3rd Fibonacci number is! Well we can follow the same pattern we used to solve for them!

As I’m sure you have realized there is a recurring (sorry, can’t help myself) theme emerging; to calculate the answer to one thing we have to calculate the answer to another. But to calculate the answer to that other thing we need to calculate the answer to another another thing. We have to keep doing this until our calculations are not based on something else. Here is where the base case mentioned in the earlier sidenote comes in. Notice in the above code that to calculate fib(4) we needed to know fib(3) and fib(2). Well, it turns out the first two fibonacci numbers are always 1. We can calculate what fib(3) by fib(2) + fib(1) both of which are 1. Once we get to this point we simply sum them up to get fib(4). Now that we know what fib(4) is we can calculate fib(5) and so on and so forth.

We are using the same formula to create a trail of calculations or rather a trail of deferred operations. Once we reach the base case all other deferred operations are calculable. To write a recursive procedure you simply need to call itself somewhere within the body of the procedure. In the case of finding the nth Fibonacci number:

function fib(n) {
  if (n < 3) {  
     return 1;
  } else {
     return fib(n - 2) + fib(n - 1)
  }
}
//the base case is any number that is less than 3 (n < 3) because //fib(2) and fib(1) are always 1
//fib(n - 2) and fib(n - 1) are each recursive calls

Going through the flow of the above code we see that if n does not equal 1 or 2, the fib()procedure will be called with (n-2) and (n-1) passed in as arguments. The same process repeats itself for each of these calls until the base case check evaluates true. Once this happens each preceding fib() can be solved.

And that is the essence of recursion! Hopefully this makes recursion a little bit more clear! In part 2, we will talk a little bit about the difference between a recursive procedure and a recursive process.

tl:dr

• Recursion is the process of solving a problem by solving smaller instances of itself
• There must be a base case in recursion; this is the most basic condition and the function does not need to call itself if this base case is true
• Once this base case is met all other calculations that have been deferred can be solved