Experiments with Recursion

Topics

1. Experiment 1
2. Experiment 2
3. Experiment 3

Experiments (What Could Go Wrong)

Experiment 1: Missing Base Case

Scenario: Write a recursive method to calculate the sum of numbers from n to 0, but forget the base case.

public int sumToZero(int n) {
    return n + sumToZero(n - 1);  // Missing base case
}

What Could Go Wrong:

• This will cause infinite recursion and eventually a StackOverflowError because there’s no base case to stop the recursion.

Solution:

• Add a base case to stop the recursion when n reaches 0.

public int sumToZero(int n) {
    if (n == 0) {
        return 0;  // Base case
    }
    return n + sumToZero(n - 1);
}

Experiment 2: Incorrect Recursive Case

Scenario: Write a recursive method to calculate the factorial of n, but make a mistake in the recursive call.

public int factorial(int n) {
    return n * factorial(n + 1);  // Incorrect recursive call
}

What Could Go Wrong:

• This will cause infinite recursion because n is increasing, not decreasing, so it will never reach the base case.

Solution:

• Ensure that the recursive call works towards the base case by decreasing n.

public int factorial(int n) {
    if (n == 0) {
        return 1;  // Base case
    }
    return n * factorial(n - 1);  // Correct recursive call
}

Experiment 3: Redundant Recursive Calls in Fibonacci

Scenario: Write a recursive method to calculate the Fibonacci sequence, but don’t account for the overlapping subproblems.

public int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);  // Overlapping subproblems
    }
}

What Could Go Wrong:

• This implementation recalculates the same Fibonacci numbers multiple times, leading to inefficiency for large n.

Solution:

• Use memoization to store already-calculated Fibonacci values to avoid redundant calculations.

public int fibonacci(int n, int[] memo) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo[n] == 0) {
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    }
    return memo[n];
}

Back to Top

Practice Exercises

Practice Recursion with exercises.