Recursion v. Iteration

How are they different?

First off, what are the differences between each? Let’s look at how the code can be written. I’m doing this online course that requires us to find out the Fibonacci series using both methods, so I will use that code as examples.

function fibonacci(num) {
   const fibArray = [0,1]
   for (let i = 2; i <= num; i++) {
      const firstNum = fibArray[i-1]
      const secondNum = fibArray[i-2]
      fibArray.push(firstNum + secondNum)
   }
   return fibArray(num)
}

Now, to explain what’s going on above. The function above finds the input as an index of the Fibonacci series as an array. I define fibArray immediately with the values of 0 and 1 because those two values are unable to create themselves using this function. So already we know an index of 0 is 0 in the array and an index of 1 is 1. For any higher values, our for loop kicks in. Since an entry in the Fibonacci series is the sum of the 2 preceding entries, we define variables retrieving those 2 preceding entries by subtracting 1 and 2 from i to get the index. Then, we push the sum of those 2 numbers into fibArray. We do that enough where once the for loop breaks, we can now find and return the inputted index in fibArray

function fibonacci(num) {
   if (num < 2) {
      return num
   }
   return fibonacci(num-1) + fibonacci(num-2)
}

And this is recursion! Whoa, why’s it so simple?! Well I’ll tell you why, chucklenuts. The secret is in calling the function within itself. Hence the name recursion! See, the function itself whittles down the initial input into 1’s, which then get added up and returned as the number in the “fibArray” (there obviously is no fibArray defined here, but we’re still working as if it’s the index of one). What does this look like?

I whipped this up in like 5 minutes in MSPaint so forgive me if it looks awful

Let’s look at this horribly drawn tree. Let’s also say we input 5 to our Fibonacci function above. The way it works is that the function continues to call itself with the numbers decreased by 1 and 2 until the input is now less than 2. We now add up each of the final branches of this tree and it gets returned to us. So, starting from the left, we add 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1, which equals 5. 5 is then returned to us! If we input 5 in the iterative version of the function, we will also get 5. However, recursive functions tend to have a lot of overhead. What’s that? Well, tune in next week and I’ll tell ya.