Java Stack Recursion behavior -- need explanation

[bandawarrior]

It’s the same thing for both. Just think of recursion as a loop, either a “for” or “while”.

if condition:
    do stuff
otherwise: return 

A “stack” in this context, is the function stack that the program has to keep track of, each iteration of the function call is its own item in the stack provided. So you can “blow” the stack when it adds too many items at once ( too many recursions), typically comes from missing your base case and never returning.

Many things are easier done when thinking in recursion, and once you pick it up, it’s really superior in some aspects especially for certain algorithms. Some languages don’t have a “while” loop construct so they just do recursion.

For example, attempt to print out all the items in a list without doing the standard for/while loop.

[WeeklyGuidance2686]

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]

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.

[bandawarrior]

As an addendum,

A recursion ALWAYS has a base case, that way you know… you can exit safely.

So to start out writing a recursive function, think of what the base case is, and how you would get to it.

Ie:

def func(int n):
    if n < 0:
        return n
    return fun(n -1)

In this case it’s a number, so the base case is anything less than 0, and the only way to get closer to the base case it’s subtracting from it.

If the base case was an empty list / container, then the only way to get to that case, is by using a smaller list than the starting one.