17.5. Recursive Count Up¶
How could you modify the previous code to make it count up instead of down? Hint: You can do this simply by swapping two lines of code.
Don’t read beyond this point until you’ve attempted to change the above code to count up.
Did you try swapping the last two lines in the countFrom method? If
not, then try it! Now, the method will print the current value before
calling itself recursively. It results in the following structure:
countFrom(5): countFrom(4) then print(5)
countFrom(4): countFrom(3) then print(4)
countFrom(3): countFrom(2) then print(3)
countFrom(2): countFrom(1) then print(2)
countFrom(1): countFrom(0) then print(1)
countFrom(0): simply return
To better understand how this works, consider the recursion tree below:
countFrom(5)
/ \
countFrom(4) print(5)
/ \
countFrom(3) print(4)
/ \
countFrom(2) print(3)
/ \
countFrom(1) print(2)
/ \
countFrom(0) print(1)
|
return
NOTE: The recursion tree traverses down the left-hand side of the
tree first. For example, after our call to countFrom(5),
countFrom(4) has to completely finish its execution before
print(5) executes. This explains why all other numbers are printed
before 5 in the output.
Here is a similar recursion tree for countFrom(3):
countFrom(3)
/ \
countFrom(2) print(3)
/ \
countFrom(1) print(2)
/ \
countFrom(0) print(1)
|
return
The recursion tree may give you the impression that all sub-problems are being evaluated concurrently. Without special code to facilitate this (e.g., using threads), these method calls occur only one at a time. To better illustrate this, here is a depiction of how the call stack changes as the recursive method calls approach and reach the base case (for an explanation of the call stack, please see the On the Call Stack aside):
immediately immediately immediately immediately
after calling after calling after calling after calling
countFrom(3) countFrom(2) countFrom(1) countFrom(0)
|------------------| |------------------| |------------------| |------------------|
| [calling method] | => | [calling method] | => | [calling method] | => | [calling method] |
|------------------| |------------------| |------------------| |------------------|
| [countFrom(3)] | | [countFrom(3)] | | [countFrom(3)] | | [countFrom(3)] |
| num = 3 | | num = 3 | | num = 3 | | num = 3 |
|------------------| |------------------| |------------------| |------------------|
| [countFrom(2)] | | [countFrom(2)] | | [countFrom(2)] |
NO OUTPUT YET | num = 2 | | num = 2 | | num = 2 |
|------------------| |------------------| |------------------|
| [countFrom(1)] | | [countFrom(1)] |
NO OUTPUT YET | num = 1 | | num = 1 |
|------------------| |------------------|
| [countFrom(0)] |
NO OUTPUT YET | num = 0 |
|------------------|
NO OUTPUT YET
Since the print statements are written after the recursive calls, we do not see any output as the program approaches the base case. However, as the recusive method calls return back to their calling methods, we begin to see the program produce the expected output. as depicted below:
immediately immediately immediately immediately
after returning after returning after returning after returning
countFrom(0) countFrom(1) countFrom(2) countFrom(3)
|------------------| |------------------| |------------------| |------------------|
| [calling method] | => | [calling method] | => | [calling method] | => | [calling method] |
|------------------| |------------------| |------------------| |------------------|
| [countFrom(3)] | | [countFrom(3)] | | [countFrom(3)] |
| num = 3 | | num = 3 | | num = 3 | OUTPUT:
|------------------| |------------------| |------------------| 1
| [countFrom(2)] | | [countFrom(2)] | 2
| num = 2 | | num = 2 | OUTPUT: 3
|------------------| |------------------| 1
| [countFrom(1)] | 2
| num = 1 | OUTPUT:
|------------------| 1
STILL
NO OUTPUT YET
17.5.1. Aside: On the Call Stack¶
You’ve seen a call stack before! When your Java programs crash from an
exception or error, the output produces a stack trace. Each line in
the stack trace represents a method call that was made (excluding
methods that have already returned), starting from main up to the
method that whose execution caused the crash.
In our depiction of the call stack, each boxed area is called a stack frame and represents a specific method call, including its local variables. You should think of this as the scratch space for that specific invocation of the method. The frames are usually depicted in a downward-moving stack as that is how they are generally stored in computer memory. If a method calls another method, then the frame for that other method is pushed/added to the bottom end of this stack. When the other method returns, its frame is popped/removed from the stack. Therefore, the frame at the end always represents the specific method where code is being executed at any given moment in time. Of course, this assumes single-threaded execution. In a multi-threaded application, there is usually one call stack per thread. In our recursion examples, we do not explicitly create new threads so we assume that only one method is ever executing at any given time.
What is presented above is good enough to establish a proper conceptual model for how method calls are handled in many programming languages. Students who are interested in taking a deep dive into how all of this works specifically in Java are encouraged to read Chapter 2: The Structure of the Java Virtual Machine in The Java® Virtual Machine Specification (Java SE 11 Edition).