أساسيات الاستدعاء الذاتي (recursion)

Written Explanation

Two parts: base case and recursive case

Every correct recursive method has:

1. A base case: an input small enough to answer directly, without calling itself.
2. A recursive case: a call to the same method with an input that is closer to the base case, combined with a little work of its own.

Factorial is the classic example. The factorial of n, written n!, is n * (n-1) * ... * 1, and by convention 0! and 1! are both 1. Notice that 4! = 4 * 3!. The factorial of a number is that number times the factorial of the next smaller number. As Java:

static int factorial(int n) {
    if (n <= 1) {
        return 1;                    // base case
    }
    return n * factorial(n - 1);     // recursive case: smaller problem
}

The base case is n <= 1. We use <= instead of == 1 so that 0 and any negative value also stop instead of recursing forever. (Negative factorials are not defined; Lesson 7 shows how the calculator rejects them before they get here.)

How it runs: frames pile up, then answers flow back

Each call to factorial gets its own frame with its own n (Lessons 4 and 5). Tracing factorial(4):

factorial(4) = 4 * factorial(3)
                   factorial(3) = 3 * factorial(2)
                                      factorial(2) = 2 * factorial(1)
                                                         factorial(1) = 1   <- base case

Phase 1, going down: no multiplication can finish yet because each frame is waiting for the call above it, so four factorial frames pile up on main: n = 4, 3, 2, 1. Phase 2, coming back: the base case returns 1; the n = 2 frame computes 2 * 1 = 2; the n = 3 frame computes 3 * 2 = 6; the n = 4 frame computes 4 * 6 = 24. Each frame is popped as it returns, handing its result to the frame below it.

The two rules that keep it safe

1. Every recursive call must move toward the base case. factorial(n - 1) shrinks n. A call such as factorial(n) or factorial(n + 1) would never reach n <= 1 from above.
2. The base case must be reachable and must come first. Check it before making the recursive call.

Break either rule and the calls never stop. The stack fills until the JVM throws a StackOverflowError (see below).

A second pattern: sum of digits

The digit sum of 123 is 1 + 2 + 3 = 6. Break a number into its last digit and "the rest": n % 10 is the last digit and n / 10 (integer division, Module 10) drops it.

static int sumOfDigits(int n) {
    if (n < 10) {
        return n;                          // one digit: that is the sum
    }
    return n % 10 + sumOfDigits(n / 10);   // last digit + sum of the rest
}

123 becomes 3 + sumOfDigits(12), then 3 + 2 + sumOfDigits(1), then the base case returns 1, giving 6. Each call has a number with one digit fewer, which guarantees it reaches a single digit. This method assumes n is not negative.

A third pattern: recursion that does not return a value

A recursive method can also be void; it acts, then calls itself with a smaller input.

static void countdown(int n) {
    if (n == 0) {
        System.out.println("Liftoff!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);
}

What goes wrong: no base case

Remove the base case from factorial:

static int factorial(int n) {
    return n * factorial(n - 1);
}

Every call makes another call. No frame ever returns, frames keep stacking, and eventually the JVM exceeds the stack size and throws the error. The Java API describes StackOverflowError as thrown when an application recurses too deeply. A real run of factorial(4) with this broken version printed:

Exception in thread "main" java.lang.StackOverflowError
	at Broken.factorial(Broken.java:3)
	at Broken.factorial(Broken.java:3)
	at Broken.factorial(Broken.java:3)
	...

The signature of the bug is the same line repeated hundreds of times. (In my run the trace listed 1,024 identical lines; the JVM caps how many it prints, so the count says nothing about how deep the stack really went.) The fix is never "catch the error". It is to add a correct base case and make sure the recursive call gets closer to it.

Recursion versus loops

Anything you can do recursively you can do with a loop (Module 13), and the reverse. A loop version of the digit sum:

static int sumOfDigitsLoop(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

Choose by clarity. A loop is usually shorter in memory (one frame, not many) and cannot overflow the stack. Recursion shines when the problem is naturally defined in terms of smaller copies of itself, such as folders inside folders or trees, which come much later. For simple counting tasks like factorial, use whichever you find clearer. Both are acceptable, and in the lab's calculator you will use a loop for power and recursion for factorial so that you practise both.