Recursion

Algorithms and Data Structures From Zero to Hero

Recursion is nothing more than a method that call itself. It’s usually a method that maybe return a value or maybe it doesn’t.

It’s conditioned on some parameter, such that when you hit some conditional at some point in time, you can stop recursing (base case).

And finally, the recursive call (where the method call itself).

Analogy

A queue

Supuse you’re in a queue and you want to know how many people are in front of you and this kind of brute force, iterative version of you says:

“Well, what I can do is I could step out line, I could run in front, and count one by one. And maybe I store these counts in some auxiliary notebook.”

And you run down this line and you get back and you say:

“I got answer, but I did a lot of work”.

So, we actually want to change this paradigm, how can I be lazy? What’s the least amount of work that I can do, and sort of break this problem down in some sort of sub structure?

And so, what I do?

I tap on the person shoulders in front of me, and I asked a very simple question:

“What number are you?”

And that person turns around and looks at me and says:

“You know I’m sorry, I don’t really know. But what I’ll do is ask the person in front of me.”

And what happens is, this process kind of continues, and it continues up until we hit some stopping condition.

This condition that we get stopped at is when we hit this person, and tap in the next person shoulder and that person says:

“Hey, what number are you in line?”

And that person is the number 1.

This is very interesting because this kind of stopping conditions to this sort of problem that we were solving.

And what that person does if takes that number, and says:

“well if the person in front of me was number 1 then I’m basically 1+1, because I count myself.”

And the person before says the same:

“if the person next to me is number X, I’m the 1+X”

And this idea unravels backwards to the original asker.

Now the person next to the original asker will say:

“Hey, there were, 14 people in front of me, I count myself and now I’m 15”.

And it turns out that we can model this problem with this simple blueprint:

1. What the least amount of work I can do (break the problem in subproblems).
2. When would the process complete (stopping condition).

We can actually write the above problem in a very simplified, minimal, piece of code:

function getMyPositionInline(person: Person) {
  if (person.nextInLine === null) {
      return 1;
  }
  
  return 1 + getMyPositionInline(person.nextInLine)
}

If we think back to those 2 questions that we have for this blueprint, we say if the first line is null then we must be the first person in line. We use this as base case (stopping condition).

Now, if we don’t satisfy this conditional, we say:

I’m going to count myself as somebody that contributes to the number of people in line. And I’m going to add the recursive call, and I’m calling myself.

And this is the interesting property of recursion, we are calling our self. But the parameter that we condition on actually further progresses us to the problem that we’re trying to solve.

So, I’m no passing the same person object into the function again, I’m actually passing a person that progress me a little bit closer to the question that I’m asking, which is how many people are in front of me.

In this really what recursion is about, how can I take some large problem and break into a bunch of subproblems such that each invocation of my method gets me a little bit closer to the problem I’m trying to solve.

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.

Cons:

• 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")
}

Let’s see what happens when you call a function.

Note: console.log is a function in JavaScript but to make things easier for this example, we’re pretending it isn’t. Jus forget about.

Suppose you call welcome(“Grace”). First, your computer allocates a box of memory for that function call.

Now let’s use the memory. The variable name is set to “Grace”. That need to be saved in memory.

Every time you make a function call, your computer saves the values for all the variables for that call in memory.

Next, you print hello, Grace! Then you call welcome2(“Grace”). Again, your computer allocates a box of memory for this function call.

Your computer is using a stack for these boxes. The second box is added on top of the first one. You print come in, grace! then you return from the function call. The box on top of the stack get popped off.

Now the topmost box on the stack is for the welcome function. When you called the welcome2 function, the welcome function was partially completed.

When you call a function from another function, the calling function is paused in a partially completed state.

All the values of the variables for that function are still stored in memory.

Now that you’re done with welcome2 function, you’re back to the welcome function, and you pick up where you left off. First you print getting ready to say goodbye… You call the bye function.

A box for that function is added to the top of the stack. Then you print Goodbye and return from the function call.

And you’re back to the welcome function. There’s nothing else to be done, so you return from the welcome function too. This stack, used to save the variables for multiple functions, is called the call stack.

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)
}

Now you call fact(3). Let’s step through this call line by line and see how the stack changes. Remember, the topmost box in the stack tells you what call to fact you’re currently on.

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

Notice that each call to fact has its own copy of x. You can’t access a different function’s copy of x.

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.

⬅️ Selection sort | Table of content | Next (Coming soon) ➡️