4.1.1.15–4.1.1.16 - Stack frames and recursion (Java)
Learn how the call stack preserves unfinished method calls and how a recursive solution combines a stopping case with a smaller problem. Trace both the calls and the returning results before writing recursive Java methods. This Java route is incomplete: runnable support pending; source tasks are written practice with no Run.
Return addresses, parameters and local state
Every active method call needs enough information to continue correctly when a called method returns. A stack frame is the call's record on the call stack: it holds its parameter values, local variables and return information. The return address identifies where execution should resume in the caller; a returned result is a different thing.
Frames follow last in, first out order. When main calls outer, the outer frame becomes active. When outer calls inner, a new inner frame goes above it. The outer frame remains underneath, preserving its unfinished work. After inner returns, its frame is removed and outer resumes at the saved position; after outer returns, main resumes. Only the most recently called unfinished method runs at that moment.
The conceptual model applies equally when a method calls itself. Each call gets a separate frame, even though the source has one method definition. The parameters and locals in one invocation do not overwrite the same-named variables of an earlier invocation. Actual Java Virtual Machine details may optimise a physical representation, but the program must behave according to this distinct-call model.
Base and general cases
A recursive method calls itself, directly or through other methods, to solve a smaller instance of a problem. A valid recursive design needs a base case with an answer that requires no recursive call, and a general case that reduces the problem toward that base case.
For non-negative n, let triangular(n) be the sum of the integers from 1 to n, with the empty sum triangular(0) = 0. Removing the last term leaves the same problem with n - 1:
static int triangular(int n) {
if (n == 0) {
return 0;
}
return n + triangular(n - 1);
}
For triangular(3), the calls have parameters 3, 2, 1 and 0. The call with 0 returns immediately. The others cannot finish their additions until their smaller calls return. Returning upward gives triangular(1)=1+0=1, then triangular(2)=2+1=3, then triangular(3)=3+3=6.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account