Practice›Java Fundamentals›Module 5. Arrays & Lists›5.5 Recursion
Task 4 of 10 · 0 solved · 10 to go0%
12345678910
You can read the problem, but answers are checked only for signed-in students. Sign in to answer →

5.5 Recursion — tracing the call stack

Lesson

Building an answer from a smaller call

Many recursive methods return a value built from a smaller recursive call. To trace one, work from the base case up: figure out what the deepest call returns, then substitute that value into the call above it, and keep going until you reach the first call.


Worked example

static int factorial(int n) {
    if (n == 0) return 1;        // base case
    return n * factorial(n - 1); // recursive case
}

Trace factorial(3) from the bottom up:

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

So factorial(3) returns 6.


▶ Try it: run this to see factorial(4). Change the number and re-run to check your own traces.



To compute factorial(4), Java first needs the value of...


Using the method above, what does factorial(3) return?


Type exactly what this program prints:

public class Main {
    static int sumTo(int n) {
        if (n == 0) return 0;
        return n + sumTo(n - 1);
    }
    public static void main(String[] args) {
        System.out.println(sumTo(4));
    }
}

Order the trace of factorial(3) from the deepest call up to the answer.


True or false?
Next task →