10 Recursion Homework

public int countWays(int n) {
    if (n == 0) return 1;
    if (n < 0) return 0;

    return countWays(n - 1) + countWays(n - 2);
}

countWays(3) –> countWays(2) + countWays(1) countWays(3) –> (countWays(1) + countWays(0)) + (countWays(0) + countWays(-1)) countWays(3) –> (1 + 1) + (1 + 0) = 3

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;
}

int[] steps = {1, 2};
System.out.println(countWaysVariableSteps(4, steps));

5

This code has a time complexity of O(2^n) was two calls are made for each increment of n. This could be remedied by storing already calculated values and not calculating for values already calculated

1. return equation(6) * equation(7) return (equation(5) * equation(4)) * (equation(5) * equation(4)) return (equation(5) * equation(4)) * ((equation(5) * equation(4)) * equation(5)) return 12 ^ 5 D. 248832

2. The program recursively iterates through every character and turns uppercase letters lowercase and lowercase letters uppercase Therefore, answer is D. tHIS IS MY FAVORITE: yAY FOR PROGRAMMING!!!

3. A. The first function call in a recursive chain, since this call will initiate the other recursive calls