CODEWITHSUNDEEP
javarecursion
Lokesh Pandey
Lokesh Pandey

Reputation: 1789

How does method call in stack gets executed - Recursion

I have a question on recursion. Whenever a base condition is hit in recursion we stop making recursive calls and then method calls in stack keeps executing and gets popped out of the memory stack one by one.

My question is once we hit that base condition and now there is no more recursive calls, so when we execute the first method call in the stack, how does the process know like it doesn't have to call the method again and has to execute it and popped it out of the stack memory ?

For e.g., Let's take a look at this piece code

private static String reverse(String str) {
    if(str.equals("")) {
        return "";
    }
    return reverse(str.substring(1)) + str.charAt(0);
}

Input : my name is slim shady

Output : ydahs mils si eman ym

When we do string reversal, now the base condition is if string is empty then no need of calling the same method, but once we hit that base condition there are method calls on stack reverse("o") + "l". Like in this image

enter image description here

How does the process know that it has to execute that method and pop out rather than making another recursive call ? Because this method reverse("o") + "l" looks like another call instead of executing it and popping it out of memory.

Upvotes: 1

Views: 665

Answers (2)

tgdavies
tgdavies

Reputation: 11421

Don't think of the stack as having pieces of code on it, but a program counter which will resume executing at a particular point in the method.

We can split reverse(str.substring(1)) + str.charAt(0) up like this (which is roughly what it will look like after it has been compiled):

tmp = reverse(str.substring(1));
tmp = tmp + str.charAt(0);
return tmp;

When the call to reverse() is made, the program counter pushed onto the stack will point at tmp = tmp + str.charAt(0);, so that's where execution will resume when the recursive call returns.

Upvotes: 1

Vincent
Vincent

Reputation: 166

I think you're thinking about how each recursive call gets pushed to the stack wrong. Since your question implies that the each recursive call still has the option to do another recursive call.

Like you said, the function will call itself until it reaches the base case. Each time that happens, the stack saves the variables into the current stack frame essentially saving the state and incrementing the stack pointer. Note that all these calls are still in the stack.

When you hit the base case, a variable is returned which means that the current stack frame can be popped and the stack pointer can be decremented. Since we have a return value of a recursive call, the previous recursive call (which has already made its recursive call) can finish its addition operation and return.

So the answer to your question is each create and save a state, which is dependent on the next recursive states finishing in order for it to finish.

Upvotes: 2

Related Questions