Recursion Homework

• 10 min read

Part A: Count Ways to Climb Stairs

Write a recursive method countWays that calculates the total number of ways the person can climb a staircase with n steps.

public class Staircase {
    public int countWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }
        return countWays(n - 1) + countWays(n - 2);
    }

    public static void main(String[] args) {
        Staircase staircase = new Staircase();
        System.out.println(staircase.countWays(4)); // Output: 5
    }
}

Staircase.main(null);

5

Part B: Trace Recursive Calls

Trace the recursive calls for the method countWays with input 3. Show how the recursion reaches the base case and unwinds.

Steps Breakdown:

  1. countWays(3) = countWays(2) + countWays(1)
    • countWays(2) = countWays(1) + countWays(0)
      • countWays(1) = countWays(0) + countWays(-1)
        • countWays(0) → 1
        • countWays(-1) → 0
      • countWays(1) = 1 + 0 = 1
      • countWays(0) → 1
      • countWays(2) = 1 + 1 = 2
    • countWays(1) = countWays(0) + countWays(-1)
      • countWays(0) → 1
      • countWays(-1) → 0
      • countWays(1) = 1 + 0 = 1
    • countWays(3) = 2 + 1 = 3

Final Result:

The total number of ways to climb a staircase with 3 steps is 3.

Part C: Modify for Variable Steps

Write a method countWaysVariableSteps that calculates the total number of ways the person can climb a staircase with n steps using the allowed step sizes.

public class Staircase {
    public int countWaysVariableSteps(int n, int[] steps) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }

        int totalWays = 0;
        for (int step : steps) {
            totalWays += countWaysVariableSteps(n - step, steps);
        }

        return totalWays;
    }

    public static void main(String[] args) {
        Staircase staircase = new Staircase();
        int[] steps = {1, 3, 5};
        System.out.println(staircase.countWaysVariableSteps(5, steps));
    }
}
Staircase.main(null);

5

Part D: Analyze Complexity

  1. Explain the time complexity of the original countWays method in terms of n without memoization.

  2. Suggest an optimization to improve the performance using memoization. Write the modified method signature and explain how it avoids redundant calls.

  3. The original countWays method is a straightforward recursive solution with exponential time complexity:

Exponential Time Complexity: O(2^n)

  • At each step, the method branches into two recursive calls: countWays(n-1) and countWays(n-2) .
  • This creates a binary recursion tree with a height of n , leading to 2^n total calls in the worst case.
  • Many subproblems are recomputed multiple times (e.g., countWays(1) and countWays(0)).
  1. Memoization stores the results of subproblems in a table (e.g., an array or a hash map) to avoid redundant calculations.

Benefits of Memoization

  • Avoids redundant calls by reusing results from previous calculations.
  • Reduces the time complexity to O(n) , as each subproblem is solved only once.
public class Staircase {
    public int countWaysMemo(int n) {
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        return countWaysHelper(n, memo);
    }

    private int countWaysHelper(int n, int[] memo) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }

        if (memo[n] != -1) {
            return memo[n];
        }

        memo[n] = countWaysHelper(n - 1, memo) + countWaysHelper(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        Staircase staircase = new Staircase();
        System.out.println(staircase.countWaysMemo(4));
    }
}
Staircase.main(null);

5
  • Recursive Logic:
    • Before computing countWays(n), the method checks if memo[n] has already been calculated. If so, it directly returns the stored result.
  • Space Optimization:
    • This approach only uses an array and avoids the overhead of a hashmap.
  • Time Complexity: O(n)
    • Each subproblem is computed only once.
  • Space Complexity: O(n)
    • Space is required for the memoization array and the recursion stack.

MC Answers

Number 1: D because the recursive calls multiply 12 repeatedly for equation(6) = 144, equation (7) = 1728, and ultimately equation(8) = 144 × 1728.

public static void main(String[] args) {
    System.out.println(equation(8));
}

public static int equation(int a) {
    if (a <= 5) {
        return 12;
    }
    return equation(a - 2) * equation(a - 1); 
}
main(null);

248832

Number 2: A because the recursion starts by checking the first character of the string. If it’s an alphabetic character, it modifies the case (uppercase to lowercase and vice versa), then recursively calls the method on the rest of the string (excluding the first character). If the character is non-alphabetic, it simply skips that character and recursively processes the next one, continuing until the entire string is processed.

Input String: “This is my favorite: Yay for programming!!!”

  • T → t (uppercase to lowercase)
  • h → H (lowercase to uppercase)
  • i → I (lowercase to uppercase)
  • s → S (lowercase to uppercase)
  • Space → Ignored
  • i → I (lowercase to uppercase)
  • s → S (lowercase to uppercase)
  • Space → Ignored
  • m → M (lowercase to uppercase)
  • y → Y (lowercase to uppercase)
  • Space → Ignored
  • f → F (lowercase to uppercase)
  • a → A (lowercase to uppercase)
  • v → V (lowercase to uppercase)
  • o → O (lowercase to uppercase)
  • r → R (lowercase to uppercase)
  • i → I (lowercase to uppercase)
  • t → T (lowercase to uppercase)
  • e → E (lowercase to uppercase)
  • Colon → Ignored
  • Space → Ignored
  • Y → y (uppercase to lowercase)
  • a → A (lowercase to uppercase)
  • y → Y (lowercase to uppercase)
  • Space → Ignored
  • f → F (lowercase to uppercase)
  • o → O (lowercase to uppercase)
  • r → R (lowercase to uppercase)
  • Space → Ignored
  • p → P (lowercase to uppercase)
  • r → R (lowercase to uppercase)
  • o → O (lowercase to uppercase)
  • g → G (lowercase to uppercase)
  • r → R (lowercase to uppercase)
  • a → A (lowercase to uppercase)
  • m → M (lowercase to uppercase)
  • m → M (lowercase to uppercase)
  • i → I (lowercase to uppercase)
  • n → N (lowercase to uppercase)
  • g → G (lowercase to uppercase)
  • ! → Ignored
  • ! → Ignored
  • ! → Ignored
public static void main(String[] args) {
    System.out.println(foo("This is my favorite: Yay for programming!!!"));
}

public static String foo(String s) {
    if (!s.equals("")) { // Continue until the string is empty
        char c = s.charAt(0); // Take the first character

        if (c >= 'A' && c <= 'Z') { // If uppercase letter
            return Character.toLowerCase(c) + foo(s.substring(1));
        } else if (c >= 'a' && c <= 'z') { // If lowercase letter
            return Character.toUpperCase(c) + foo(s.substring(1));
        }
        return foo(s.substring(1)); // Ignore non-alphabetic characters
    }
    return ""; // Base case: empty string
}
main(null);

tHISISMYFAVORITEyAYFORPROGRAMMING

Number 3: B. because the base case in a recursive function is the condition that halts the recursion by returning a value, preventing it from calling itself indefinitely.

Extra Game using recurssion

This is a Formula 1 based game with recurssion logic. I made it to practice my recursion skills and to continue my practice.

import java.util.Random;
import java.util.Scanner;

public class F1RaceGame {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Welcome to the Enhanced Formula 1 Recursion Game!");
        
        System.out.print("Enter the number of cars: ");
        int numCars = scanner.nextInt();
        
        System.out.print("Enter the number of steps to finish the race: ");
        int raceLength = scanner.nextInt();
        
        startRace(numCars, raceLength);
    }

    public static void startRace(int numCars, int raceLength) {
        Random random = new Random();
        String[] carNames = {"Car 1", "Car 2", "Car 3", "Car 4", "Car 5"};
        
        for (int i = 0; i < numCars; i++) {
            int carPosition = 0;
            System.out.println(carNames[i] + " is racing...");
            race(carPosition, raceLength, carNames[i], random);
            System.out.println();
        }
    }

    public static void race(int carPosition, int raceLength, String carName, Random random) {
        if (carPosition >= raceLength) {
            System.out.println(carName + " has crossed the finish line!");
            return;
        }

        int move = random.nextInt(4);

        switch (move) {
            case 1:
                carPosition += 3;
                System.out.println(carName + " got a boost! Moving forward 3 steps.");
                break;
            case 2:
                carPosition -= 2;
                System.out.println(carName + " had a pit stop! Losing 2 steps.");
                break;
            case 3:
                carPosition -= 1;
                System.out.println(carName + " hit an obstacle! Moving back 1 step.");
                break;
            default:
                carPosition += 1;
                System.out.println(carName + " is at position: " + carPosition);
        }

        race(carPosition, raceLength, carName, random);
    }
}
F1RaceGame.main(null);

Welcome to the Enhanced Formula 1 Recursion Game!
Enter the number of cars: Enter the number of steps to finish the race: Car 1 is racing...
Car 1 had a pit stop! Losing 2 steps.
Car 1 hit an obstacle! Moving back 1 step.
Car 1 hit an obstacle! Moving back 1 step.
Car 1 hit an obstacle! Moving back 1 step.
Car 1 got a boost! Moving forward 3 steps.
Car 1 got a boost! Moving forward 3 steps.
Car 1 is at position: 2
Car 1 had a pit stop! Losing 2 steps.
Car 1 is at position: 1
Car 1 is at position: 2
Car 1 got a boost! Moving forward 3 steps.
Car 1 has crossed the finish line!

Car 2 is racing...
Car 2 hit an obstacle! Moving back 1 step.
Car 2 got a boost! Moving forward 3 steps.
Car 2 had a pit stop! Losing 2 steps.
Car 2 got a boost! Moving forward 3 steps.
Car 2 had a pit stop! Losing 2 steps.
Car 2 is at position: 2
Car 2 had a pit stop! Losing 2 steps.
Car 2 hit an obstacle! Moving back 1 step.
Car 2 is at position: 0
Car 2 hit an obstacle! Moving back 1 step.
Car 2 is at position: 0
Car 2 had a pit stop! Losing 2 steps.
Car 2 is at position: -1
Car 2 hit an obstacle! Moving back 1 step.
Car 2 is at position: -1
Car 2 is at position: 0
Car 2 had a pit stop! Losing 2 steps.
Car 2 got a boost! Moving forward 3 steps.
Car 2 hit an obstacle! Moving back 1 step.
Car 2 got a boost! Moving forward 3 steps.
Car 2 got a boost! Moving forward 3 steps.
Car 2 has crossed the finish line!

Car 3 is racing...
Car 3 got a boost! Moving forward 3 steps.
Car 3 hit an obstacle! Moving back 1 step.
Car 3 got a boost! Moving forward 3 steps.
Car 3 has crossed the finish line!

Car 4 is racing...
Car 4 is at position: 1
Car 4 hit an obstacle! Moving back 1 step.
Car 4 had a pit stop! Losing 2 steps.
Car 4 hit an obstacle! Moving back 1 step.
Car 4 is at position: -2
Car 4 is at position: -1
Car 4 hit an obstacle! Moving back 1 step.
Car 4 had a pit stop! Losing 2 steps.
Car 4 got a boost! Moving forward 3 steps.
Car 4 had a pit stop! Losing 2 steps.
Car 4 had a pit stop! Losing 2 steps.
Car 4 is at position: -4
Car 4 had a pit stop! Losing 2 steps.
Car 4 is at position: -5
Car 4 hit an obstacle! Moving back 1 step.
Car 4 got a boost! Moving forward 3 steps.
Car 4 got a boost! Moving forward 3 steps.
Car 4 had a pit stop! Losing 2 steps.
Car 4 hit an obstacle! Moving back 1 step.
Car 4 got a boost! Moving forward 3 steps.
Car 4 is at position: 1
Car 4 hit an obstacle! Moving back 1 step.
Car 4 hit an obstacle! Moving back 1 step.
Car 4 hit an obstacle! Moving back 1 step.
Car 4 hit an obstacle! Moving back 1 step.
Car 4 got a boost! Moving forward 3 steps.
Car 4 got a boost! Moving forward 3 steps.
Car 4 is at position: 4
Car 4 is at position: 5
Car 4 has crossed the finish line!

Car 5 is racing...
Car 5 is at position: 1
Car 5 hit an obstacle! Moving back 1 step.
Car 5 hit an obstacle! Moving back 1 step.
Car 5 got a boost! Moving forward 3 steps.
Car 5 is at position: 3
Car 5 got a boost! Moving forward 3 steps.
Car 5 has crossed the finish line!