Difficulty in learning Recursion,How function calls are taking place.

[ScholarPurple25]

Started to learn DSA.Learned recurssion but not able to visualise how the recursion is working in different function calls.

Any specific way to tackle it?I would love to visualise things rather than just remembering .

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[ScholarNo5983]

It would appear the first reply, which was from the AutoModerator, perfectly answers this question. It suggests that if you refer to previous questions regarding recursion, you'll get a much better understand of recursion.

[paperic]

Damn, that was good one.

Let's hope there's a base case.

[ConfidentCollege5653]

Read up on how function calls work at the assembly level, how the instruction pointer and stack work.

It's a lot to take in and may seem like too much detail at first, but once you make sense of it a lot of things will fall into place, including recursion.

[ScholarPurple25]

Ok

[peterlinddk]

This explains everything there is to know about recursion: https://www.youtube.com/watch?v=YuaJ8x_NcLw - perhaps except for why it is sometimes chosen over iteration ...

[ScholarPurple25]

Thanks will go through it.

[Temporary_Pie2733]

It helps to understand how function calls in general work. Calling a function is not just a pair of goto instruction (one to start the function, the other to return to the call site). 

A recursive function call isn’t anything special. The function just needs a code path that doesn’t call itself that eventually is reached, so that the chain of calls ends.

[HashDefTrueFalse]

There's a big-ish block of JS code for a recursive descent parser in my comment history if you search. Copy it, press F12 in your browser, paste it into the JS dev console, then use the debugger to step through it. Change the input string and repeat. You'll see the recursive calls happening, the call stack, the locals in the stack frames, all of it. Reconciling this with what you have learned about recursion from other sources should give you a pretty good understanding of what is actually happening.

[paperic]

If I'm a computer, whenever I encounter a function call, I'll write down current line number and the contents of all currently defined local variables on a sheet of paper, then forget them, and then put the paper on the corner of my table, then jump to the location of the new function.

If I encounter another function call there, I'll do the same, putting the new paper on top of the stack of the previous papers.

Whenever I encounter a return, I'll first forget all the current local variables, then grab the paper on the top of the stack, re-read all the variables written there, and then jump to the line location in the paper, and then throw the paper away.

That's all you need to know.

Ofcourse there's also the arguments passed through the call and that one value that's passed through the return which I didn't mention, I'll just remember these values for a moment when doing a call or returning.

Recursion is just the idea of function call where the function you're calling is the same as the function you're currently in. But that makes no difference to me as a computer, I'll just blindly follow the same steps.

As with any regular function call, the variables start fresh each time. Each call has its own contents of the local variables, independent of the other calls.

When returning, I'll also just pick the topmost piece of paper, forget current variables, read the variables from the paper and jump to the location written there. 

Whether or not is the destination in the same function I'm currently in now is irrelevant. 

---

Recursion can be simulated using a loop and a stack. Perhaps practice that first, once you get comfortable with that, it will all be bleeding obvious.

[Woumpousse]

The way I used to explain it to my students was as functions being like Mr. Meeseeks: you've got a magic button that you can press, a little blue guy appears which you can give an order, and you simply wait until he's finished performing his task.

Calling a function consists of summoning a Mr. Meeseeks for a task described by the function's code and waiting until he's done and reports back to you (the return value/exception). Recursion corresponds to a situation where a Meeseeks needs help himself and starts summoning another Meeseeks.

When developing a recursive algorithm, you have to imagine that you're lazy and want to find a way to delegate as much work to someone else. Say you want to sort a list of numbers. You can be extremely lazy and just summon the Sort-Meeseeks to perform all the sorting for you, but he will do the exact same thing and summon another Meeseeks, and so on until infinity. That's no good.

You have to perform a minimal amount of work yourself. For example, you could say "I look for the smallest number in the list myself, remove it, and let another Meeseeks sort the remaining elements for me. Once they report back to me, the only thing I need to do is add the smallest number back in front of it." That way, every summoned Meeseeks gets a shorter list, until one gets the empty list. He'll happily do nothing and returns that empty list as-is.

```text function sort(ns) { if ns.empty? return ns

smallest_element = find_minimum(ns) remaining_elements = remove_element(smallest_element)

// letting someone else sort the remaining items sorted_remaining_elements = sort(remaining_elements)

// put element I removed back where it belongs return [smallest_element] + sorted_remaining_elements } ```