The End

What is Recursion?

Instead of recapping all the subjects covered in CS50, I decided to spend time on a fundamental that was briefly introduced in CS50 which is recursion.
Just like iteration, recursion is a technique to solve a problem that involves repetition.
A recursive function typically calls itself to break down a bigger problem into smaller subproblems (recursive case) and uses a condition (base case) to stop the recursive calls, thereby avoiding an infinite loop.
Below is the implementation of a multiply function.
The first implementation uses a recursion and the second one an iteration:


const multiply_recursive = (a,b) => {

    if( b == 1 ){
        return a;
    }

    return a + multiply_recursive(a, b - 1);
}


const multiply_iterative = (a, b) => {

    let total = 0;

    for(let i = 0; i < b ; i++){

        total = total + a 

    }

    return total;
}

As you can see a recursive function can be written iteratively and an iterative function can be written recursively.

Recursion and the call stack

One of the fundamental difference between recursion and iteration is how the code is executed.
A recursive function goes through 3 stages:
1- A winding stage where we are adding function calls to the call stack.
2- A base case where a specific value is reached.
3- An unwinding stage where the functions in the call stack are evaluated one by one to return the value of the parent function.
Let's take a look at how the recursive function works:

Stage 1: winding


  multiply_recursive(5,4);
  
      ↓
  multiply_recursive(5,4) → returns 5 + multiply_recursive(5,3);
  
      ↓
  multiply_recursive(5,3) → returns 5 + multiply_recursive(5,2);
  
      ↓
  multiply_recursive(5,2) → returns 5 + multiply_recursive(5,1);

Stage 2 : base case


multiply_recursive(5,1) -> returns 5 (base case reached)

Stage 3 : unwinding
Since we reached the base case and we know that multiply_recursive(5,1) = 5; we can get the value of multiply_recursive(5,2), etc..


multiply_recursive(5,1) = 5 // base case 


multiply_recursive(5,2) = return 5 + 5 // 10


multiply_recursive(5,3) = return 5 + 10 // 15


multiply_recursive(5,4) = return 5 + 15 // 20

The problem with recursion

By looking at the 3 stages of recursion, we can directly see how recursion can cause performance issues.
Calling multiply_recursive(5,10000) for example, will add 10000 calls on the call stack which will cause a stack overflow.
Calling multiply_iterative(5,10000) on the other hand will create a single function call on the call stack.
Both recursion and iteration have a time complexity of O(n).
However, recursion has a space complexity of O(n) due to the call stack, while iteration has a space complexity of O(1) since it does not use additional memory for function calls.

Tail recursion

There is a way to mitigate the performance issue of recursion.
Consider the following function:


const multiply_recursive_tail = (a,b,total) => {


    if ( b == 0){
        return total
    }

    return  multiply_recursive_tail ( a, b -1 , total + a)

}


multiply_recursive_tail(5,4,0) // 20

In this example we are incrementing the value of total on each call.
Once we reached the base case, we only have to return the total variable.
This technique is called tail recursion.
In tail recursion there is no unwinding phase as the result is directly returned when we reach the base case.
The winding phase is also different : each new function replaces the previous one and the call stack does not grow.

So when should you use recursion over iteration?

It is almost always better for the machine to use an iteration over a recursion.
A recursion could be more elegant and more readable for a human to implement when solving problems that involves a recursive structure like:
Tree traversal (e.g., DOM traversal, binary trees)
Graph traversal (DFS, backtracking)
Divide and conquer algorithms (QuickSort, MergeSort)
Mathematical sequences (Fibonacci, factorial)