DEV Community

Cover image for The Recursion Explanation I Wish I Had Read As A Self-Taught Developer
Gus Pear 🍐
Gus Pear 🍐

Posted on • Updated on

The Recursion Explanation I Wish I Had Read As A Self-Taught Developer

It took me several attempts to understand recursive functions.

Once I understood how it works, I figured I didn't completely understand 2 things:

  1. Function’s Return Value
  2. The Callstack

Once I understood these 2, recursion made sense.

This post is how I’d teach my beginner-self recursion if I could go back.

#1 Function’s Return Value

When a function returns a value, the function itself is replaced by the return value.

Let me try to exemplify:

This is a function that returns the square of a number

function square(x) => x * x;
Enter fullscreen mode Exit fullscreen mode

This:

const num = 1 + square(3);
Enter fullscreen mode Exit fullscreen mode

Is the same as:

const num = 1 + 9;
Enter fullscreen mode Exit fullscreen mode

square(3) is "replaced" by 9, since 9 is the value that the function returned.

function return value

Cool? Great.

Do you remember that in Maths sometimes the order or the operations mattered? This is the case when working with functions. The code interpreter can’t add 1 to square(3) before it knows what the heck is the value of that square(3) returns. So functions have to be executed before the other calculations on the same line.

Example:

function square(x) => x * x; //line 1
const num = 1 + square(3);   //line 2
console.log(num) //10        //line 3
Enter fullscreen mode Exit fullscreen mode

The interpreter will run the above code in the following order:

  1. Line 1 (read the function declaration)
  2. Line 2 (Oh there is a function here, let's call this function passing the value 3 into it)
  3. Line 1 (function is called with 3 and returns with the value 9)
  4. Line 2 (it replaces the function with 9 and now can calculate 9 + 1 and assign it to num)
  5. Line 3 Finally we log 10 to the console.

The takeaway is that every time there is a function call, the interpreter:

  • Stops on that line and calls the function
  • It runs the function code with the value passed in(if any)
  • It goes back to the line that called it
  • Replaces the function call with the returned value
  • Resume from there

It is essential to understand this to understand recursion(this was one of the things I had problems with that made it harder to understand recursion).

#2 The Callstack

The call stack is how the interpreter(like the javascript interpreter in this browser) keeps track of the functions called by the script.

That is how the interpreter knows how to come back to the line that has called the function.

I’d like to think of it as a box to store the books you read and in which page and line you stop at each.

Say you are in your local library.

You start reading the book β€œSapiens”. On page 72 line 87 it mentions the diprotodon(the biggest marsupial to walk on earth) which itches your curiosity. So you put a marker on the page and write down the line you are at and put the book in the box.

box with a book

Then you find a book about the diprotodons. But on page 94 line 138 it mentions the giant sloths and again curiosity kicks in. You put a marker on page 94 and write the line you are at on it and put it in the box.

2 boxes with books

As you read more about the giant sloths you realize it’s time to go home. You put another marker on page 121 line 147 and put the book in the box.

3 boxes with books

The next morning you rush to the library to finish your readings.

How do you know in what book, page, and line you left off? Since you were organized with your stack of books and markers, the answer is easy. Just pick the top book from the box, the marker inside the book will tell the page and line.

Know you can make your way back to the initial book("Sapiens") and keep reading until the end(or until curiosity strikes again)

The analogy is:

  1. The box is the call stack
  2. Each book is a function call
  3. Each marker is in which line the function was called

If I'd translate this example into code it would look something like this:

function readSapiens(){
   //read until page 72 line 87
   readDiprotodonsBook();
   //finish reading sapiens(when we are back from reading about diprotodons)
}

function readDiprotodonsBook(){
   //read until page 94 line 138
   readGiatSlothsBook();
   //finish reading diprotodon's book(when we are back from reading about giant sloths)
}

function readGiatSlothsBook(){
   //read until page 121 line 147
   debugger
}

readSapiens();
Enter fullscreen mode Exit fullscreen mode

If you hit f12 now, copy this code, paste it on the console, hit enter, and go to the sources tab you can see the call stack.

It will look like this:

the callstack
The code is paused inside the third function call.

See that there is no magic, everything is built on top of data structures.

Now we are prepared to go over an actual recursive function example.

Basic Example

The simplest example I can think of is a function that adds all numbers until the number you passed in.

function addNums(x){
   if(x === 1) return x;
   return x + addNums(x - 1);
}
Enter fullscreen mode Exit fullscreen mode

Note: I am not taking into account 0 or negative numbers to simplify the example.

addNums(3) //6
addNums(5) //15
Enter fullscreen mode Exit fullscreen mode

Let's go through it line by line:

function addNums(x){          //line 1
   if(x === 1) return x;      //line 2
   return x + addNums(x - 1); //line 3
}                             //line 4
                              //line 5
let sumThree = addNums(3);    //line 6
console.log(sumThree); //6    //line 7
Enter fullscreen mode Exit fullscreen mode
  1. [Lines 1 to 5]: Smooth execution, it just declares the function(now we can call it when need to)

  2. [Line 6]: The interpreter declares the variable sumThree but before it assigns the value addNums(3) he realizes that it is a function, so it has to call the function first(passing 3 into it) to then assign the return value to the variable sumThree

2.1. [Waiting on Line 6]: It calls the function on line 1, passing 3 into it. 3 is not equal to 1 so we move past line 2. On line 3 we should return 3 + addNums(3 - 1) but wait, this is another function call. So it has to call it first passing 2 into it.

2.2. [Waiting on Line 6 [waiting on Line 3]]: It calls the function on line 1, passing 2 into it. 2 is not equal to 1 so we move past line 2. On line 3 we should return 2 + addNums(2 - 1) but wait, this is another function call. So it has to call it first passing 1 into it.

2.3. [Waiting on Line 6 [waiting on Line 3 [waiting on Line 3]]]: It calls the function on line 1, passing 1 into it. This time we hit the base case. 1 === 1 is true, so for the first time we return a value from a function call.

2.4. [Waiting on Line 6 [waiting on Line 3]]: It goes back to line 3 of the previous function call. It now can calculate 2 + addNums(2 - 1) because it now knows that addNums(2 - 1) is 1. So this function now can return 3.

2.5. [Waiting on Line 6]: Lastly it goes back to the initial call on line 6. It can now calculate 3 + addNums(3 - 1) because it now knows that addNums(3 - 1) is 3. So this function now can finally return 6.

  1. [Line 7]: It logs 6 to the console.

I also tried to explain it visually(to the best of my abilities), have a look:

Image description

Conclusion

If you read this far, first I want to thank you, it means a lot to me. Second, if you got lost at any point in this post, can you do me a favor?

Leave a quick comment saying where I lost you.

I'll try to improve this post so it can help you that like me once had a hard time understanding recursion.

Thanks again for reading!

If you like this article:

Leave a comment (You can just say hi!)
Let's connect on Twitter @theguspear

Catch you next week,

Gus.

Top comments (43)

Collapse
 
jonrandy profile image
Jon Randy πŸŽ–οΈ • Edited

It's possible to implement recursion without filling up the stack at all - with trampolining. This technique can be useful when dealing with recursive functions that fast run out of memory.

Collapse
 
defufna profile image
Ivan Savu

Trampolining only works for tail call recursion, which is when the recursive call is the last call in the function. However, such functions can be easily written as a loop in either case.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Hey Jon! Thanks for taking the time to leave a comment!

I hadn't heart of trampolining before. Just had a quick look at the article you linked and it seems awesome.

I'll take my time and read it later.

Thanks for adding to the post.

Have a great rest of your week!

Collapse
 
mneme profile image
Alex T

haha! I didn't know the word "recursion function" but I always got confused about the function that calls itself whenever I had quiz in Javascript. More accurately, I am puzzled at how a function could call itself for. I wonder under what situation or purpose that we will use recursion function?

thank you so much! I love the frame by frame explanation as it gives clarity.

Maybe it is good to intro on recursion function.
" - Recursion is a process of calling itself. A function that calls itself is called a recursive function.

  • A recursive function must have a condition to stop calling itself. Otherwise, the function is called indefinitely. -Once the condition is met, the function stops calling itself. This is called a base condition"
Collapse
 
ant_f_dev profile image
Anthony Fung

I've found one of the best uses of recursion is traversing nodes in a data tree. As each node typically has the same data structure, a function can call itself, passing in a child/parent node and so on until it finds the right data.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Spot on Anthony, this is a great use case and example.

Thanks for your comment!

Collapse
 
mneme profile image
Alex T

Thank you for sharing~

Collapse
 
gustavupp profile image
Gus Pear 🍐

Hey Alex, it's good to hear from you again!

You can pretty much replace any function that uses loops with recursion(you probably shouldn't).

I am planning on a follow up post with more realistic examples.

Have a great week

Collapse
 
mneme profile image
Alex T

thank you so much for your effort and generosity in sharing in details.

Thread Thread
 
gustavupp profile image
Gus Pear 🍐

Thank YOU for always stopping by to leave a comment Alex!

Collapse
 
byronsalty profile image
Byron Salty

Thanks for this - I'll definitely pass along.

One thought for improvement. I think it would be clearer what is happening in the books analogy if you made it more explicit that you're jumping out to read the referenced book and coming back to finish the book...

function readSapiens(){
   //read until page 72 line 87
   readDiprotodonsBook();
   //finish reading the book
}
Enter fullscreen mode Exit fullscreen mode

This could also allow you to reuse the analogy when talking about tail recursion. This example is NOT tail recursive because you're jumping out mid book but you could make it tail recursive by:

function readSapiens(){
   //read until page 72 line 87
   saveNameOfBookToRead();
   //finish reading the book
   readDiprotodonsBook();
}
Enter fullscreen mode Exit fullscreen mode

And now it even mentally you can see how this is now just reading three books in a row instead of reading half of one, reading another book halfway, then reading a full book, then going back and reading the second half, then going back and reading the second half of the first book. Heh. It really illustrates why tail recursion is a thing,

Collapse
 
gustavupp profile image
Gus Pear 🍐

Hey Byron, massive thanks for the comment!

I was meant to do that but ended up forgetting.

Suggestion added.

Have a great week!

Collapse
 
thumbone profile image
Bernd Wechner • Edited

Just an observation that in your Basic example, counter to your claim, you fail to add the 1. There are two easy ways to fix that πŸ˜‰. I'd also add the #javascript tag as your examples and some of your prose clearly assume a JS context.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Hey Bernd, how are you?

I coudn't find where I failed to add 1. If you've got a few extra minutes, can you point out where it is so I can fix it to the readers?

Thanks for taking the time to comment and have a great week!

Collapse
 
thumbone profile image
Bernd Wechner

Hey, thanks for checking in. I think I was wrong, and should eat my hat ;-).

function addNums(x){
   if(x === 1) return x;
   return x + addNums(x - 1);
}
Enter fullscreen mode Exit fullscreen mode

does, in fact add one at the end after all. I tripped myself up with poor recursive comprehension ;-). Well done to check in on it. Personally, I'd probably write it:

function addNums(x){
   if (x === 1) return 1;
   return x + addNums(x - 1);
}
Enter fullscreen mode Exit fullscreen mode

Which is of course identical (just a little more explicit to my mind). This of course fails for addNums(0) or for that matter any negative number (which will blow the stack) but that is another story altogether.

Silly me anyhow. I felt so sure at the time that this doesn't add one at the end, when it sure as heck does on the second line, when x is 2 and I could have worked that out simply by running though: addNums(1), and addNums(2) in my mind .... but I was too sleep-deprived and/or lazy yesterday and opened my mouth to put my foot in it.

Good job catching that!

Thread Thread
 
gustavupp profile image
Gus Pear 🍐

It's all good Bernd! We have all been there hehe.

Thanks for clearing things up

Have a great rest of your week!

Collapse
 
cubiclesocial profile image
cubiclesocial

Recursion can be subtle. When I was making this Offline Forms tool:

github.com/cubiclesoft/offline-forms

I ran into the problem that switching "pages" resulted in another function call on the stack. It would probably take thousands of page switches before the loaded page would run out of stack space, but it could technically happen.

I tried various things before I gave up and just went old-school. The solution I used was to put the information about the next page to jump to into a semi-global variable and then wait for an already registered interval to fire. When the interval callback runs, it sees that it has some work to do and switches the page. Result? Call stack stays flat. But it is a hacky workaround involving regular polling of a variable.

Collapse
 
gustavupp profile image
Gus Pear 🍐

What a pain hey CubicleSocial hehe

It seems like you found a good way around it and that is what we do as devs right? find solutions.. you nailed this one.

Thanks for taking the time to leave a comment and enjoy the weekend!

Collapse
 
chrisgreening profile image
Chris Greening

Yeahhh you nailed it right on the head! Fantastic article Gus thanks for sharing :D

I really love your book analogy and subsequent translation into code, I always find analogizing concepts with tangible examples (i.e. a stack of books to demonstrate a program's call stack) to be the most effective method of teaching and you did a really great job of that

Definitely wish I had this article when I was first learning recursion as chaining value returns back through the stack is the concept I probably struggled with the most - weird ideas to wrap your head around lol definitely need some solid analogies to hammer it home!

Collapse
 
gustavupp profile image
Gus Pear 🍐

Heyy Chirs!! It feels very motivating to read a comment like yours haha (honestly)

This is exacly how I tend to understand things, by having a "real" example of the abstract concept. It just clicks haha

Thanks a lot for taking the time to leave this awesome an motivator comment man.

Have a greay day my dude!

Collapse
 
eekee profile image
Ethan Azariah

Good explanation! I love the book stack analogy. :)

I had the call stack and returns down before I first heard of recursion, but it took me ages to understand that the termination condition must be easily derivable from the function arguments. It didn't help that, back in the 80s & 90s, recursion was always introduced with a fibbonacci sequence function which I thought was far more elegantly implemented by swapping the values of two variables within a loop. I took an instant dislike to it. :) Swapping two variables is a bit clunky, but I don't see how a function call is better.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Glad you liked it Ethan!

In my case when I first read a recursive function I was following the code line by line and got lost on the return(calling the function again)

That is why I try to explicitly show a line by line approach

Thanks for sharing a bit of your experience with recursion Ethan

Have an awesome day

Collapse
 
coderamrin profile image
Amrin

saved for later.
I've been struggling to understand recursion lately.
thanks for writing this Gus.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Het Amrin, how are you??

I know the feeling.. I mostly wrote what would've helped me when I first tried to understand recursion.

Hopefully it will help you too.

Once you read, let me know how it went, it there is any questions please post it here and I'll try to answer.

Have a nice rest of your week

Collapse
 
coderamrin profile image
Amrin

Will do Gus.
appreciate your help :)

Collapse
 
lovestaco profile image
Athreya aka Maneshwar

Nicely explained, there is a small mistake in the diagram In the final return 3+3=6.
It's alright if it's not editable.
Good work.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Thanks for catching the typo Amneshwar!

The first draft I did with a function returning x * x but thought the x + x was even
simpler.

All fixed, have a nice rest of your week

Collapse
 
raithlin profile image
Stephen Metcalfe

Excellent write-up and explanation, Gus. Saved and most definitely sharing. Thanks for taking the time to share this.

Collapse
 
gustavupp profile image
Gus Pear 🍐

Heyy Stephen!! how is it going brother?

Thank YOU for leaving this awesome comment haha!

It means a lot to me. β™₯