Understanding Recursion in 5 minutes

Ever since I started studying programming and algorithms, recursion was always a concept I avoided at any cost. I simply adopted the iterative approach for any problem I faced. However, after a semester studying Data Structures, Discrete Mathematics and Functional Programming at Ryerson University, recursion became pretty clear to me. Don’t be like me and embrace recursion because is not as hard as it looks. Strong functional programming languages like Haskell and Elixir rely heavily on recursive functions because they don’t have state (non-mutable variables and no global scope). Thus if you ever had to learn or build something in a functional programming language, you have to feel comfortable with recursion.  

Iterative vs Recursive

Lets see two different algorithms that solve the same problem, sum all the numbers in a given range of integer numbers.

In the iterative solution, we use a loop to go through all the numbers in range and on each iteration, we update the sum variable that will be later used as a return value. Usually, iterative algorithms are faster because uses less memory because tend to use the same variables in each iteration.


function sumNumRange(a, b){
   sum = 0;
      for(var i = a; i < = b; i++){
         sum += i;
      }
      return sum;
}

In the recursive version, we simply return the smallest number in range plus the function itself, but this time we discard smallest number we just called on the summation by incrementing the smallest number of the range. Recursion requires more memory since the same function is called several times until the base case is reached. The number of times the function is called is equivalent to the number added to memory. In the iterative version, the function is only stacked in memory once.


function sumNumRange(a, b){
   //until a does not reach b
   if(a<b){
      return a + sumNumRange(a+1, b);
   }
   //base case: a reached b
   //if a >= in the first call, just returns b
   else{
      return b;
   }
}

 

Base case and General case

It is important to know that is mandatory for a recursive function to have a base case and a general case. If your recursive function never reaches the base case, there is a potential possibility that it will call itself endlessly without stopping. Eventually, this will cause your program to run out of memory and crash. In the example above, the based case is reached when the smallest number in range (a) is equal or bigger than the largest number in range (b). In each call a gets close to b, just like an loop.
The goal of the general case is to split the main problem into tinier sub-problems up to the point where it hits the base case and stops calling the function. At each step, the results of the sub-problems are combined to produce a solution to the main problem.

Trace calls

What helps quickly understand and track recursive functions is trace calls. Trace calls are easy to do on paper and helpt you track step by step the process of recursion. Check below the trace call for the sumNumRange function.

sumNumRange(1, 5)
= (1 + sumNumRange(2, 5))
= (1 + (2 + sumNumRange(3, 5)))
= (1 + (2 + (3 + sumNumRange(4, 5))))
= (1 + (2 + (3 + (4 + sumNumRange(5, 5))))) [Base Case]
= (1 + (2 + (3 + (4 + (5)))))
= (1 + (2 + (3 + (9))))
= (1 + (2 + (12)))
= (1 + (14))
= 15

Each method call returns a number in range plus the next function until the base case is reached. Once reached all the call are returned back to the first call of the function.

Types of Recursion

Recursion can be quite flexible and you can solve problems quite differently. Some type of recursion are going up (Example shown above), going down, division in halves and edges to middle. Check my CodePen to see all this types of recursion applied in the sumNumRange.

Applicable Cases of Recursion

One of the best applications of recursion is the fibonacci numbers and the factorial calculation.

Fibonacci Numbers
Initial sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Formula: F(n) = F(n-1) + F(n-2)


function fibonacci(x) {
   if (x <= 1) return 1;
   return fibonacci(x - 1) + fibonacci(x - 2);
}

Factorial
Example: 3! = 3*2*1 = 6


function factorial(x){
   if(x == 1){
      return 1;
   }
   else{
      return x * factorial(x-1);
   }
}

Ready to face Recursion?

I believe you got a better understanding of how recursion works and eventually you can implement some of your solutions with it. If you want to practice check w3resource. It has several exercises in JavaScript where recursion can be applied.

I am a software developer in the making and I am blogging to review what I learn and to try help others the same position. Don’t give up and practice.


Also published on Medium.

Leave a Reply

Your email address will not be published. Required fields are marked *

*