The Call Stack

Part of: Recursion

How Recursion Actually Runs When a method is called, Java creates a stack frame : a small block of memory holding that call's parameters , local variables , and the spot to return to. These frames pile up on the call stack , a last-in-first-out (LIFO) structure. Each recursive call pushes a new frame. When a call finishes (returns), its frame is popped off, and control returns to the caller. Tracing Through the Stack Consider counting down: Calling countDown(3) builds the stack like this: - Push countDown(3) - prints 3 - calls countDown(2) - Push countDown(2) - prints 2 - calls countDown(1) - Push countDown(1) - prints 1 - calls countDown(0) - Push countDown(0) - base case, returns - pop - countDown(1) resumes, returns - pop - countDown(2) resumes, returns - pop - countDown(3) resumes, returns - pop Output: 3 2 1. Work Before vs. After the Call The position of your work matters: - Code before the recursive call runs on the way down (during pushes). - Code after the recursive call runs on the way back up (during pops). If we move the print after the call, the numbers come out reversed (1 2 3) because each print waits for the deeper call to finish first. StackOverflowError The stack

Challenge: Print On The Way Up