Recursion and Iteration(Javascript)

In coding, we often run into scenarios of doing things repeatedly when manipulating certain types of data. Luckily the problem solving techniques of iteration (/looping) and recursion exist to help programmers perform repeated processes in efficient and extensible ways.

Iteration/Loops

Loops are used to execute the same block of code a specified number of times. There are many different kinds of loops — most familiarly, the for loop and the while loop. In general, for loops are great when we know how many times the loop should run and while loops are perfect for scenarios where we want the loop to break based on a condition being satisfied.

When loops aren’t enough —Recursion

Under the hood, both recursion and iteration depend on a condition so as to know when to stop. While looping is a group of code run over and over, recursion is a process always applied to a function. It is a problem-solving technique, where the function is applied to a new, broken down instance of itself. This is repeated until the base case is reached.

In other words, the recursive function calls itself either directly or indirectly.

A recursive function has two main parts.

1. Base case — a terminating condition which allows the function to come to an end
2. Recursive case — the portion of the function that calls itself.

Recursion is useful because it provides a clean and simple way to write code. As a result, while recursive and iterative programs have the same problem-solving powers(see the Fibonacci sequence below), we can use recursion to solve complicated problems more efficiently than using iteration. A common example among programmers is the Tower of Hanoi.

However, it is important to note that because of how a recursive function executes, it has greater space requirements than iterative program. All its functions will remain on the stack until the base case is reached. It also has greater time requirements because of function returns and calls computing overhead. Forgetting the base case in a recursive function will lead to STACK OVERFLOW.

Solving the Fibonacci sequence using both iteration and recursion

The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers.

An example of the sequence can be seen as follows:

Solution using iteration:

function fib(n){
  let arr = [0, 1];
  for (let i = 2; i < n + 1; i++){
    arr.push(arr[i - 2] + arr[i -1])
  }
 return arr[n]
}
fib(4)
=> 3

Solution using recursion:

function fib(n) {
 //base case
 if (n < 2){
    return n
  } 
  // recursive case 
  return fib(n - 1) + fib (n - 2)
}
=> fib(4) = fib(3) + fib(2) = ( fib(2) + fib(1) ) + ( fib(1) + fib(0) ) …
=> 3

You can see from above that the recursive case is a bit more elegant in its implementation. It doesn’t need to assign variables or push into the array.

Hopefully now that you have seen the power of recursion you feel armed to tackle more challenging algorithms. To learn even more about recursion check out the below resources.

Resources

Recursion Made Simple

Recursion - GeeksforGeeks