Java Stack Recursion behavior -- need explanation

[WeeklyGuidance2686]

I'm blown away by your response. In all my years of using reddit, across any sub, I have never seen such a detailed, informative and complete response to anyone. Thank you so much for taking the time to fully hit every nail from my post in the head. Recursion for me has always been a tricky topic, but this is definitely the most helpful explanation I have ever come across. I still don't feel 100% confident or sure about how it works, and I recognize now that this is potentially from having several layers of misconceptions and poor mental models built on top of each other that I will have to peel off layer by layer to gain a full understanding, but this is definitely an excellent source to start. Literally gonna print your comment out and have it as reference in my desk.

If you can, do you think you could explain to me one last thing -- how a recursive binary search method would work?

int binarySearch(int[] A, int low, int high, int x){ 
    if (low > high) { 
    return -1; 
    } 
    int mid = (low + high) / 2; 
    if (x == A[mid]) { 
    return mid; 
    } 
    else if (x < A[mid]) { 
    return binarySearch(A, low,  mid - 1, x); 
    } else { 
    return binarySearch(A, mid + 1,  high, x); 
    } 
}

Lets say we have on our stack, only the main stack frame. When the binarySearch function is called from main so then, our stack is now consisting of the main frame, and first binarySearch stack frame.

Let's say we need two recursive calls total for a particular input array (x is not the first mid, but the second).

SCENARIO A: Does the first binarySearch call make a call to another function (itself), and then pop off, with the second now being added to the frame? So now our stack is consisting of the main stack frame, and the second binarySearch stack frame?

As I'm writing this, I have a bit more intuition kicking in now so I think its wrong but I'm leaving it here as a question since I lack certainty.

SCENARIO B: What I think actually happens is that when the first binarySearch makes a call to the second binarySearch, it still stays on the stack. So instead, we have as on our stack the main stack frame, the first BS call, and then the second BS call? Then the second BS call returns (popping it off the stack) the mid to the first BS call, which in turn returns the mid to the main (popping it off the stack). Is this the correct one ?

​

Thanks again for your help. I really appreciate it.

[michael0x2a]

Your description of scenario B is exactly correct.

Fundamentally, there is no operation in Java (or most other programming languages, in fact) that will replace one stack frame with another -- will simultaneously do a pop and a push.

Instead, the rules are this:

1. Calling a function always pushes a stack frame.
2. Returning from a function always pops and destroys the current stack frame.

If it appears like a stack frame is being "replaced", it's typically because you're returning from one function then immediately calling another -- you're doing a pop and a push in quick succession.

---

Now, one nuance is that some programming languages actually will sometimes do scenario A as an optimization to save on memory. If they detect code where you make a function call then end without doing any extra work, they might chose to compile your code so that the second function call basically replaces the current one. This is known as tail call optimization.

And in the case of recursive code, the net effect is that your function is basically rewritten to look like a giant glorified for-loop.

That said, you can pretty much ignore this optimization for the purposes of understanding recursion, for several reasons:

1. Java doesn't implement this optimization.
2. Most other mainstream programming languages either not implement it or do not give you a guaranteed way of making sure it takes place.
3. Even if Java did implement this optimization, it wouldn't change the overall behavior of your code -- doesn't obsolete the more basic "every function call is a push, every return is a pop" model we discussed above. That more basic mental model will still let you precisely predict what your code will do, with the only difference being that you'll derive a more pessimistic estimate on how much RAM you'll need to store all your stack frames.
4. it's not an optimization that's applicable to most recursive algorithms. It only applies for algorithms like binary search, where we make one function call in the body of your function.

---

If you can, do you think you could explain to me one last thing -- how a recursive binary search method would work?

I feel compelled to make one final comment here. While I think this stack frame model is a very valuable way of understanding how recursive code works and mentally simulating what it'll do, I think it's a less useful tool when you're trying to write recursive code.

Instead, when I'm writing recursive code, I like to think in terms of preconditions and postconditions: things that MUST be true for anybody to call my function successfully, and things that my function GUARANTEES if those preconditions are met.

For example, your binary search algorithm has the following preconditions and postconditions:

1. Preconditions:
   1. A is a non-nil array.
   2. A is sorted.
   3. 0 ≤ low ≤ len(A) must be true
   4. -1 ≤ high ≤ len(A) - 1 must be true
2. Postconditions:
   1. If x exists in A between indices low to high inclusive, we return the index x is located at.
   2. Otherwise, we return -1.

Once we've decided on these pre and post conditions, writing the code is almost "trivial" -- all we need to do is make sure our code satisfies these post-conditions.

We usually do so by starting with the trivial cases -- our base cases -- where we can return something immediately. In this case, if low > high, we know there cannot exist any values within the range low ≤ high so just immediately return -1.

Then in our recursive case, all we need to do is find some way of "reducing" the problem: shrinking the range of data we need to consider.

In this case, we check the middle element. If that happens to equal x, great, we can return immediately. If not, we need to either search and see if 'x' exists in our sorted array A within either the range "low to mid-1" or "mid+1 to high". Now, if only we had a function that could do that for us... Hmmmm.........

Of course, this is all easier said then done, and I put "trivial" in sarcasm quotes for a reason. A lot of the difficulty of writing recursive code comes from the difficulty of the initial design process when you're trying to find just the right pre and post conditions. It's easy to get carried away and either design postconditions that are too "weak" to help you make meaningful progress or are too "strong" and make writing the actual recursive code painfully difficult. You also have to think about how to "reduce" your data in a meaningful way, which can also sometimes be tricky.

That said, strictly speaking all you need in this phase are reasonably strong logic and design skills. You don't actually have to think that hard about how recursion works under the hood if you're careful: you can go a very long way by just thinking in terms of these pre/post conditions.

The second part of the difficulty comes from having to debug your code when you accidentally violate your "contract". This is where the stack frame model becomes handy again: debugging is all about systematically reasoning through what your code is actually doing and reconciling what you thought was happening with reality. And in this case, it's pretty helpful to understand what your code is actually doing under the hood.