# Recursion

## Analogy

1. What the least amount of work I can do (break the problem in subproblems).
2. When would the process complete (stopping condition).
`function getMyPositionInline(person: Person) {  if (person.nextInLine === null) {      return 1;  }    return 1 + getMyPositionInline(person.nextInLine)}`

## Pros and Cons

Pros:

• Bridges the gap between elegance and complexity.
• Reduces the need for complex loops and auxiliary data structures.
• Can reduce time complexity easily with memoization.
• Works really well with recursive structures like trees and graphs.
• Can lead to out of memory errors / stack overflow exceptions.
• Can be unnecessary complex if poorly constructed.

## The call stack

Internally your computer uses a stack internally called the call stack. Let’t see in action. Here’s a simple function:

`function welcome(name) {  console.log(`Welcome, \${name}!`  wellcome2(name)  console.log("getting ready to say goodbye")  bye()}function welcome2(name) {  console.log(`come in, \${name}!`}function bye() {  console.log("Goodbye")}`

## The call stack with recursion

Let’s look this in action with the factorial function. factorial(5), and it’s defined like this: 5! = 5 * 4 * 3 * 2 * 1. Similarly, factorial(3) is 3 * 2 * 1. Heres a recursive function to calculate the factorial of a number:

`function fact(x) {  if (x === 1) {    return 1  }    return x * fact(x-1)}`
`CODE                CALL STACKfact(3);                  |x = 3|----------------------------------if x == 1;                |x = 3|------------------------------------else:                     |x = 3|-------------------------------------// A RECURSIVE CALL:return x*fact(x-1);       |x = 3||x = 2|------------------------------------------// NOW WE ARE IN THE SECOND CALL TO fact. x is 2if x == 1;                |x = 3||x = 2| <- THE TOPMOST FUNCTION                                            CALL IS THE CALL WE ARE                                             CURRENTLY IN--------------------------------------------else:                     |x = 3||x = 2| NOTE: BOTH FUNCTION CALL                           👆     👆           HAVE A VARIABLE NAMED X                                          AND THE VALUE OF X IS DIFERENT                                           IN BOTH.--------------------------------------------return x*fact(x-1);     |x = 3||x = 2||x = 1|👈 YOU CAN'T ACCESS THIS                                 👆              CALL X FROM THIS CALL                                                   AND VICE VERSA.--------------------------------------------if x == 1                 |x = 3||x = 2||x = 1|-------------------------------------------return 1;                |x = 3||x = 2| ↪️|x = 1|⤵ THIS THE FIRST BOX TO GET                                                    POPPED OFF THE STACK,                                                WHICH MEANS ITS THE FIRST                                            CALL WE RETURN FROM-------------------------------------------return x * fact(x-1)      |x = 3| ↪️ |x = 2|⤵ RETURNS 2       👆   👆 THIS CALL RETURN 1       X IS 2---------------------------------------------return x * fact(x-1)      ↪️ |x = 3| ⤵ RETURNS 6       👆   👆 THIS CALL RETURN 2       X IS 3`

## Summary

• Recursion is when a function calls itself.
• Every recursive function has two cases: the base case and the recursive case.
• All functions calls go onto the call stack.
• The call stack can get very large which takes up a lot of memory.

--

--

## More from Kemil Beltre

Software Engineer passionate about learning, creating new things and sharing my knowledge in the process.