Call Again

The Recursion Technique — JavaScript

4 min readFeb 18, 2021

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. (Wikipedia)

With the recursion technique, we can replace code written iteratively with clean and simple code. Recursion does not optimize for performance, instead, it prioritizes readability. Some problems that are difficult to solve iteratively are incredibly intuitive to solve recursively.

Call of Duty

There are 2 must-have features in a recursive function:

base case(s)
recursive case(s)

The base case is the stopping condition (usually a conditional). Input that matches the base case produces a result once, it returns a value. Without a base case (or a proper base case), the function will have infinite recursion and cause a stack overflow.

If the input does not match the base case, it reaches the recursive case. In the recursive case, the function calls itself with different input. With each call, the input MUST change to ensure it eventually reaches the base case. If the input never reaches the base case, the function will (you guessed it!) have infinite recursion and cause a stack overflow.

Call Stack

Behind the magic of recursion is the call stack. It is very difficult, albeit impossible, to understand recursion without understanding the call stack. The call stack is a specific implementation of the stack data structure. A stack is a LIFO (last in, first out) data structure — the last thing to be pushed onto the stack is the first thing to be popped off the stack.

To visualize the call stack, picture a deck of cards.

Now, place one card on the table. Next, place a second card on top of the first card. Continue placing the cards on top of each other (one at a time) until all 52 cards are stacked on the table.

Now, remove the cards from the pile one at a time. First, remove the last card that was placed on the pile. Continue removing the cards one at a time. Finally, the first card placed on the pile is the last card removed.

With recursion, the function calls are stored on the call stack. Therefore, the last call placed on the stack is the first one resolved, and the first call placed on the stack is the last one resolved.

Call Me

Let’s look at a classic recursion example in JavaScript.

Udemy — JavaScript Algorithms and Data Structures Masterclass

This function has the required features for a recursive function:

base case: if(num === 1) return 1;

If the input is 1, we have reached the end of the factorial since the last integer to multiply is 1. This is a proper base case because it returns a value.

2. recursive case: return num * factorial( --num);

With each recursive call, the input is decremented. This ensures that the input will eventually be equal to 1 and, therefore, reach the base case.

Call to Action

Ok, so we have our base and recursive cases and we understand the call stack. But, how is the function returning the correct solution?

CALL STACK4th in: return 1                // factorial(1) -> base case reached
3rd in: return 2 * factorial(1) // factorial(2) -> recursive call
2nd in: return 3 * factorial(2) // factorial(3) -> recursive call
1st in: return 4 * factorial(3) // factorial(4) -> initial call

Each function call is waiting for the return value of the call that was after it (i.e. 1st in is waiting on 2nd in which is waiting on 3rd in, etc.). Once the base case is reached, the calls resolve in reverse order. The function call that was pushed on to the stack last, is resolved first (i.e. 4th in is now 1st out).

1st out: return 1
2nd out: return 2 * factorial(1)
3rd out: return 3 * factorial(2)
4th out: return 4 * factorial(3)

When the function ends (base case) or JavaScript sees the return keyword (recursive case), the compiler will remove the function from the call stack.

1st out is resolved and removed

1st out: resolves to -> 1
2nd out: return 2 * factorial(1)
3rd out: return 3 * factorial(2)
4th out: return 4 * factorial(3)

2nd out is resolved and removed

2nd out: resolves to -> 2 * 1 -> 2
3rd out: return 3 * factorial(2)
4th out: return 4 * factorial(3)

3rd out is resolved and removed

3rd out: resolves to -> 3 * 2 -> 6
4th out: return 4 * factorial(3)

4th out is resolved and removed

4th out: resolved to -> 4 * 6 -> 24

Finally, factorial(4) returns 24

Call When

Recursion is best for cases where an iteration is getting too intricate or we want to write code that is easier to read and understand.

Call of the Wild— Sample Problems

📚 Resources 👀
Understanding Recursion in JavaScript with Confidence
When Should You Use Recursion
Udemy — JavaScript Algorithms and Data Structures Masterclass