Recursion & Recursion & Recursion!

What is it?

What is recursion? Basically a process in which a function calls itself directly or indirectly, and the corresponding function is called a recursive function.

Recursion is good for solving problems that can be broken down into smaller subsets of the original argument. It is especially good for working on things that have many possible branches and can become too complex for an iterative approach.

It’s actually hard for me to always wrap my head around it, a function call that calls itself adding to the call stack, and itself and itself continually with smaller arguments until it reaches a predetermined end of the line and then returns back up the call stack? It can be confusing on exactly what you want function to do every time it hits.

But here I go trying to explain it!

To begin let’s start with an example-

A Simple Example

Here is a very simple recursive function where the sum of all preceding positive numbers up to the argument number are added together otherwise called summation.

Function sum(number){
    if(number <= 1) return number;
    return number + sum(number-1)
}
sum(5)
=> 15

In this example the function is called and is added to the call stack.

Call Stack

The call stack is used to keep track of multiple function calls, what functions have been called and when.
It operates on a first in last out basis.

Kind of like building blocks, when a function is called it goes in the stack, if another function is called that function goes in the stack and does not get removed from the stack until it is complete. It then gets popped off the call stack which in turn the previous function gets complete and then gets popped off the call stack.

Recursive function foo() without base case getting called until stack overflow

The sum function takes a number as the argument, it checks if the number is less than or equal to 1. This is our base case for the recursive function.

The Base Case

The base case is the condition that stops the recursive function from going on forever. Every recursive function needs at least one base case.
In the example above the base case is 1 or less than in case a 0 is entered. The base case is decided based on the nature of the function, here 1 is chosen as the function continually subtracts 1 from the argument to add together all preceding numbers. As 1 has no positive preceding number it is our base case and smallest subset of the argument.

Continuing…

So here if the number is not ≤ to 1 the function will call itself with the number directly preceding it as an argument.
So sum(number-1) or sum(4) is being called and because the argument is 4 and has not satisfied the conditional, the function then calls itself again with sum(number-1) or sum(3).
This recursive calling will continue until we meet our base case if(number <= 1) return number;the conditional in the code that ends the recursive loop.

Now that the condition is met 1 will be returned and that function call will get popped off the call stack, which is added to the argument of 2 from the next function and will return 3 then get popped off the call stack.

 // Here is what is going on
sum(5) => sum(4) => sum(3) => sum(2) => sum(1)
// argument is less than or equal to 1 condition achieved!
// now we start to drop function calls off the call stack
sum(1) conditional hit returns 1 
sum(2) + 1 returns 3 
sum(3) + 3 returns 6 
sum(4) + 6 returns 10 
sum(5) + 10 returns 15

The return of the recursive sum function is 15 and all the functions have been popped off of the call stack, woo!

A More Complicated Example

not really just more steps…

const arr = [38, 27, 43, 3, 9, 82, 10];
function mergeSort(arr){
  if (arr.length < 2) return arr;
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const temp = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]){
      temp.push(left.shift());
    }
    else{
      temp.push(right.shift());
    };
}
  while (left.length){
    temp.push(left.shift());
  };
  while (right.length){
    temp.push(right.shift());
  };
  return temp;
};
// console.log(mergeSort(arr));

mergeSort use a divide and conquer strategy to recursively go through an array splitting the argument in half during each invocation of the function, continually dividing the argument until the base case of array.length < 2 or 1 element in the array.
The array argument of 1 element for both left and right invocations of the function is then returned to be evaluated by the merge function.
The merge function takes in the return value of the two recursive calls and compares them for the lesser value and pushes this value to a temporary array, this will continue until one of the arrays are empty.

const temp = [];
while (left.length && right.length) { // left =[38] right = [27]
if (left[0] <= right[0]){ // 38 <= 27 - false
      temp.push(left.shift());
    }
else{
      temp.push(right.shift()); // temp = [27]
    };

The merge function then continues adding the remaining values of the other array to the temporary array by evaluating if either left or right arrays still contain any elements.

while (left.length){   // 1 = true
    temp.push(left.shift()); // temp = [27, 38]
  };
while (right.length){   // 0 = false
    temp.push(right.shift());
  };

This sorted array is now the return value of the merge function call and will get pushed down the call stack to be compared to the other divisions and invocations of the mergeSort recursive function call.

while (left.length && right.length) {
// left =[27, 38] right = [3, 43]
if (left[0] <= right[0]){ // 27 <= 3 - false
      temp.push(left.shift());
    }else{
      temp.push(right.shift()); // temp = [3]
    };

// continuing the while loop left =[27, 38] right = [43]
if (left[0] <= right[0]){ // 27 <= 43 - true
      temp.push(left.shift()); // temp = [3,27]
    }else{
      temp.push(right.shift()); 
    };
// continuing the while loop left =[38] right = [43]
if (left[0] <= right[0]){ // 38 <= 43 - true
      temp.push(left.shift()); // temp = [3,27,38]
    }else{
      temp.push(right.shift()); 
    };
// out of the left/right comparison while loop as left.length == 0
// moving on to 
while (right.length){   // right.length == 1
    temp.push(right.shift());
  };
// temp = [3,27,38,43]
// return temp 
// next [3,27,38,43] will be evaluated against [9,10,82]
// in the same manner until [3,9,10,27,38,43,82]

Recursion vs iteration

Geeks for Geeks states:

Usage: Usage of either of these techniques is a trade-off between time complexity and size of code. If time complexity is the point of focus, and number of recursive calls would be large, it is better to use iteration. However, if time complexity is not an issue and shortness of code is, recursion would be the way to go.

Recursion: Recursion involves calling the same function again, and hence, has a very small length of code. However, as we saw in the analysis, the time complexity of recursion can get to be exponential when there are a considerable number of recursive calls. Hence, usage of recursion is advantageous in shorter code, but higher time complexity.

Iteration: Iteration is repetition of a block of code. This involves a larger size of code, but the time complexity is generally lesser than it is for recursion.

Which means recursive functions that use a large amount of function calls to the call stack can be taxing on memory e.g. finding the 10th fibonacci number requires 89 function calls. That’s a lot of overhead when getting up into larger numbers like say the 50th fibonacci number which takes 20,365,011,074 function calls.

function fib(num){
  if(num <= 1) return num;
  return fib(num - 1) + fib(num - 2);
}
// I didn't allow this to finish it was taking so long

Thats alot of function calls, without memoization it takes a very long amount time to complete the task. I didn’t let the operation finish , it was taking so long, not entirely sure it would have.

This would be a good case for an iterative approach for the time and space complexity of the above recursive function (Big O Notation, I plan on writing an article on this soon).
Either way the iterative approach here is much quicker and less taxing on time and memory.

function fib2(num){
  let prevPrev = 0;
  let prev = 1;
  let currentNumber;

  if(num < 2) return num;
  for(let i = 1; i < num; i++){
    currentNumber = prevPrev + prev;
    prevPrev = prev;
    prev = currentNumber;
  }
  return currentNumber;
}
console.log(fib2(50))
=>12586269025
//The results were immediate 

On the other hand, using memoization in the recursive call changes the time and space complexity to something more manageable as well.

Memoization

Memoization is the storing output of a function in a cache, passing the cache to each function call and making the function check if the value is in the cache before computing it.
This allows us to pull return values that have already been computed, meaning on the recursive tree, patterns that have already been found do not need to be recursively called as they are stored in the memo object and can just be looked up and returned. Saving memory and speeding up the recursive operation.

function fib(num, memo = {}){
  if (num in memo) return memo[num];
  if(num <= 1) return num;
  memo[num] = fib(num - 1, memo) + fib(num - 2, memo);
  return memo[num]
}
console.log(fib(50));
=> 12586269025
// The results were immediate compared to the non-memoized version I
// didn't allow to finish

Here is the benchmark of the two functions:

function benchmarkFib(){
  console.time('fib:')
  for(let i = 0; i < 100000; i++){
    fib(50)
  }
  console.timeEnd('fib:')
  console.time('fib2:')
  for(let i = 0; i < 100000; i++){
    fib2(50)
  }
  console.timeEnd('fib2:')
}
benchmarkFib()
fib:: 232.563ms
fib2:: 11.37ms

Here we can clearly see the iterative function is much quicker than the recursive function. Yet the recursive function is IMO is easier to read and more intuitive, of course this seems to be a subjective matter.

A good few guidelines to follow are as follows.

When to use Recursion:

• When time and memory are not an issue.
• When the iterative approach requires you to manage your own call stack
• And when the code can be less complicated and easier to read with fewer lines

Here is a diagram with some key differences:

Because the more you know!

My Summary

Recursion can be used on datasets where the iterative approach can become to complicated.
If if can be solved in a few lines of code as opposed to a giant mess of who knows what is going on, a few lines of code are better as long as time and memory are a huge factor.
They say it’s more elegant but I’d stick with it as a utility, honestly the iterative approach will more often be the best solution as long as the don’t have to manage your own call stack and its still readable.

I think it’s a great tool to have and I enjoyed researching this and adding it to my tool belt. I hope you got something out of this!

And always thanks for reading.