DEV Community

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

Gus Pear 🍐 on February 16, 2023

It took me several attempts to understand recursive functions. Once I understood how it works, I figured I didn't completely understand 2 things: ...

Read full post

Jon Randy 🎖️ • Feb 16 '23 • 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.

Ivan Savu • Feb 16 '23

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.

Gus Pear 🍐 • Feb 16 '23

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!

Alex T • Feb 18 '23

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"

Anthony Fung • Feb 21 '23

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.

Gus Pear 🍐 • Feb 22 '23

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

Thanks for your comment!

Alex T • Feb 22 '23

Thank you for sharing~

Gus Pear 🍐 • Feb 19 '23

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

Alex T • Feb 20 '23

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

Gus Pear 🍐 • Feb 21 '23

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

Byron Salty • Feb 18 '23

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
}

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

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,

Gus Pear 🍐 • Feb 19 '23

Hey Byron, massive thanks for the comment!

I was meant to do that but ended up forgetting.

Suggestion added.

Have a great week!

Bernd Wechner • Feb 21 '23 • 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.

Gus Pear 🍐 • Feb 22 '23

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!

Bernd Wechner • Feb 23 '23

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

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

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!

Gus Pear 🍐 • Feb 23 '23

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

Thanks for clearing things up

Have a great rest of your week!

cubiclesocial • Feb 18 '23

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.

Gus Pear 🍐 • Feb 18 '23

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!

Chris Greening • Feb 17 '23

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!

Gus Pear 🍐 • Feb 18 '23

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!

Ethan Azariah • Feb 22 '23

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.

Gus Pear 🍐 • Feb 23 '23

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

Amrin • Feb 22 '23

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

Gus Pear 🍐 • Feb 22 '23

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

Amrin • Feb 22 '23

Will do Gus.
appreciate your help :)

Athreya aka Maneshwar • Feb 22 '23

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.

Gus Pear 🍐 • Feb 22 '23

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

Stephen Metcalfe • Feb 22 '23

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

Gus Pear 🍐 • Feb 22 '23

Heyy Stephen!! how is it going brother?

Thank YOU for leaving this awesome comment haha!

It means a lot to me. ♥

Kadiri Talitu (Coded Salis) • Feb 19 '23

What a brilliant way to pass on your knowledge!
More grease to your elbows 💪

Gus Pear 🍐 • Feb 19 '23

Hey Kadiri, how are you man?

A comment like this reminds me that I am going in the right direction.

Thanks a lot for taking the time to comment.

Kadiri Talitu (Coded Salis) • Feb 19 '23

Yeah, man... The quality of the post is well worth it 🙂

Gus Pear 🍐 • Feb 21 '23

Thanks brother! ♥

Arinze Obi • Feb 17 '23

Brilliant 👏

Gus Pear 🍐 • Feb 18 '23

Thanks you Arinze! ♥

Youdiowei Eteimorde • Feb 16 '23

Awesome article, I love your diagrams.

Gus Pear 🍐 • Feb 16 '23

I am glad you liked them Youdiowei!!

A diagram can tell more than a thousand words they say haha

ebuka anthony • Feb 16 '23

Nice Write-up. It made me understand to a high degree, the practical concept of function calling in Js OOP

Gus Pear 🍐 • Feb 16 '23

Glad to hear that Ebuka!

Let me know if there is any unclear points.

have a great weekend

Lucas Barret • Feb 16 '23

When I've began to learn code. I wish I had this explanation thanks a lot. At that time I did not even know what a stack was. :')

Gus Pear 🍐 • Feb 16 '23

Hey Lucas!
Me too.. haha

That is the goal! I'm happy that you liked it!

Have a great weekend

Anik K Dev • Feb 18 '23

I lost at 2.4.
Can you please explain that again?

Gus Pear 🍐 • Feb 18 '23

Hey Anik, sure.

At 2.3 is when for the first time a function returns an actual value 1(and not call another function).
At 2.4 the previous call was 2 + addNums(2 - 1) so addNums(2 - 1) is replaced by the value 1 so this function now can also return a real value 2 + 1 which is 3(that will be fed into the previous call...)

Have a look at the highlights here: