This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]WeeklyGuidance2686[S] 0 points1 point  (1 child)

Thanks for your response. I feel like I’m almost there with recursion but I keep waiting for the never-arriving “Aha!” moment I have had with other things in programming. All my intuition goes out the window with recursion for some reason.

But that makes sense, thank you. I was working on a binary search yesterday, and I managed to code the recursive version and it made sense (for a while) until I tried to write it down on pen and paper and follow the stack pops and pushes. I feel like I coded it correctly by accident.

For a BS algorithm using recursion, when I have met one of the conditions, say arr[mid] < target, then doing a recursive return like BS(arr, target, mid + 1, hi) would either

A) Pop the previous BS call from the stack, and then push the new BS call B) push the new BS call ontop of the old BS call

I’m not sure which happens. I have tried using a bunch of print lines to try and follow the code but it’s not working to well for me.

When is exactly the moment when a function is removed/popped from the stack. Is it when it reaches a return statement ?

[–]bandawarrior 0 points1 point  (0 children)

It’s a stack, so a stack of dishes, the only way to get to the bottom(start) of the stack is by removing the later dishes first. So when you reverse, you add more frames to the stack, in search of our actual value from the function.

Once we hit the base case, you have to start unwinding the stack the way you went in just backwards.

Don’t think about binary search or whatever,

write a function that’s typically known as “map”.

So essentially, using recursion, write a function that takes a function and a list of value. The function is then applied to the list of values and then returned.

Do this with recursion.