# Call Again

## The Recursion Technique — JavaScript

In computer science,

recursionis 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.

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

`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

Udemy — JavaScript Algorithms and Data Structures Masterclass