How is recursion implemented in Java? My question is about what happens behind when a recusrsive method is executed in Java. I vaguely understand that it uses the Stack, but i am looking for a clear explanation with example.
Asked
Active
Viewed 2,156 times
0
-
1Please try the following : http://www.javamex.com/tutorials/techniques/recursion_how.shtml – Chetter Hummin May 22 '12 at 10:50
-
Its "The Stack" not Stacks ;) – Ozair Kafray May 22 '12 at 10:51
-
@AmitBhargava Link explains what a recursion is, but i am looking for how it is implemented in Java – 18bytes May 22 '12 at 10:51
-
You may want to check out the link below https://rawisglenn.medium.com/recursion-explained-with-inception-movie-analogy-c185fdad9bb5 – lonelearner Mar 25 '22 at 10:07
2 Answers
11
Recursion isn't handled much differently in Java than in other (imperative) languages.
There's a stack which holds a stack frame for every method invocation. That stack is the call stack (or simply just "stack", when the context makes it clear what is meant). The element on the stack are called "stack frames".
A stack frame holds the method arguments passed in and the local variables of a method invocation (and possibly some other data, such as the return address).
When a method invokes itself (or, in fact, any method) then a new stack frame is created for the parameters and local variables of the newly-called method.
During the method execution the code can only access the values in the current (i.e. top-most) stack frame.
This way a single (local) variable can seemingly have many different values at the same time.
Recursion isn't handled any other way than normal method calls, except that multiple stack frames will represent invocations of the same method at the same time.
Joachim Sauer
- 302,674
- 57
- 556
- 614
-
1I was going to say "Except for the tail call recursion optimisation." but apparently the Java VM still doesn't support it. http://stackoverflow.com/questions/3616483/why-does-the-jvm-still-not-support-tail-call-optimization – Michael Anderson May 22 '12 at 11:19
-
@MichaelAnderson: simply speaking tail recursion optimization is "simply" re-using the current stack frame when the compiler/runtime realizes that it's no longer needed except for the return address. It doesn't fundamentally change the way the stack (and recursion) works. – Joachim Sauer May 22 '12 at 11:21
0
when a method if invoked it needs space to keep its parameters, its local variables and the return adress this space is called activation record (stack frame).
Recursion is calling a method that happens to have the same name as the caller, therefore a recursive call is not litterally a method calling it self but an instantiation of a method calling another instantiation of the same original. these invocations are represented internally by different activation records which means that they are differentiated by the system.
Mouna Cheikhna
- 38,870
- 10
- 48
- 69