Status of system stack by recursion

Question

enter image description here

Can somebody explain what is status of the system stack? And how it is connected to the binary search?

Answer 1

Apparently the question is about two separate things, namely

1. binary search, which can be implemented both iteratively and recursively;
2. the difference between a recursive and an iterative implementation concerning the call stack.

Binary search refers to finding an object in a sorted list (or a sorted array). The strategy is to examine the object in the middle of the list; either the desired object is found or not. If it is not found, it must be searched in either the left half or the right half of the list; the irrelevant half can be discarded.

This approach can be implemented either iteratively, where auxiliary indices governing the search are maintained. Alternatively, it can be implemented recursively, where the binary search for the relevant half is called again.

In an iterative implementation, there is only one call to the binary search, which means that no new stack frames are generated for the search. In a recursive implementation, a new stack frame is generated for each recursive call. As each step discards at least half of the search space, this means that at most log(n) new stack frames (one for each recursive call) are generated, where n is the number of objects in the initial list.

Answer 2

SHORT: Basically, the stack is a portion of memory the system uses to store the state of the function when you call it (parameters, variables etc..). For longer description you can consult this great link. The binary search is not connected to the stack, in fact, any piece of code can use the stack. In your case, you are asked is to describe the state of the stack (as the one in the picture you provided) when you call your binary search function.