Scope & Recursion

Scope decides where a variable can be used: a variable declared in a block exists only inside it. Recursion is a method calling itself — an elegant way to solve problems that contain smaller copies of themselves, like walking folders or nested data.

Block scope

void main() {
    int total = 0;
    for (int i = 0; i < 3; i++) {
        int doubled = i * 2;
        total += doubled;
    }
    System.out.println(total);
    System.out.println(doubled);
}

Main.java:8: error: cannot find symbol

A variable lives from its declaration to the end of the enclosing block { }. doubled and the loop variable i don't exist after the loop; total, declared outside, does.

Method scope

int counter = 0;

void increment() {
    int step = 1;
    counter += step;
}

void main() {
    increment();
    increment();
    System.out.println(counter);
}

2

Parameters and local variables exist only while their method runs. To share state between methods, use fields — like counter here, declared outside any method (lesson 23 covers fields properly). Java doesn't allow a local variable to shadow another local in an enclosing block, which prevents a whole category of confusing bugs.

Keep scope small

Declare variables as close as possible to where they're used, in the smallest block that needs them. Code is easier to follow when each variable has a short, obvious life.

Recursion

long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

void main() {
    System.out.println(factorial(5));
    System.out.println(factorial(20));
}

120
2432902008176640000

Every recursive method needs:

• A base case that returns without recursing (n <= 1).
• A recursive case that calls itself on a smaller problem (n - 1), moving towards the base case.

factorial(5) = 5 × factorial(4) = 5 × 4 × factorial(3) … = 120.

Stack overflow

int forever(int n) {
    return forever(n + 1);
}

void main() {
    try {
        forever(0);
    } catch (StackOverflowError e) {
        System.out.println("StackOverflowError: the recursion never stopped");
    }
}

StackOverflowError: the recursion never stopped

Each call takes space on the call stack. Without a reachable base case, the stack runs out. Even correct recursion can overflow when it goes very deep (many thousands of levels); a loop is then the better tool.

Where recursion shines

int sumDigits(int n) {
    return n < 10 ? n : n % 10 + sumDigits(n / 10);
}

String reverse(String s) {
    return s.isEmpty() ? "" : reverse(s.substring(1)) + s.charAt(0);
}

int binarySearch(int[] sorted, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (sorted[mid] == target) return mid;
    return sorted[mid] < target
        ? binarySearch(sorted, target, mid + 1, high)
        : binarySearch(sorted, target, low, mid - 1);
}

void main() {
    System.out.println(sumDigits(90417));
    System.out.println(reverse("stressed"));
    int[] data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    System.out.println(binarySearch(data, 23, 0, data.length - 1));
}

21
desserts
5

Recursion fits naturally when data is recursive (trees, folders, nested comments) or a problem splits into halves (binary search, merge sort). For simple counting, loops are usually clearer and faster.

Memoisation

long[] memo = new long[91];

long fib(int n) {
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

void main() {
    System.out.println(fib(10));
    System.out.println(fib(90));
}

55
2880067194370816120

The naive Fibonacci recursion recalculates the same values exponentially many times. Storing results (memoisation) makes it instant.

Try it yourself

Write a recursive method that counts down and then back up.

4 3 2 1 0 1 2 3 4