Recursion

Algorithms and Data Structures From Zero to Hero

Analogy

A queue
  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.
  • Slowness due CPU overhead.
  • 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 STACK
fact(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 2
if 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|👈[3] YOU CAN'T ACCESS THIS[3]
👆[2] CALL X FROM THIS[2] 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.

--

--

Sometimes I write about technical topics and sometimes about what I feel like.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kemil Beltre

Sometimes I write about technical topics and sometimes about what I feel like.