FRQ

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 int countWays(int n)

public int countWays(int n) {
    
    // Base case: If n == 0, return 1 (one way to stay where you are).
    if (n == 0) { 
        return 1;
    }

    // Base case: If n < 0, return 0 (no valid ways).
    if (n < 0) { 
        return 0;
    }
    // Recursive case: Combine the results of taking 1 step from n-1 and 2 steps from n-2.
    return countWays(n-1) + countWays(n-2);

}

countWays(4) // returns 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.

countWays(3);

n is not 0, and n is not < 0, so proceed

return countWays(3-1) + countWays(3-2);

splits into:

For countWays(2):

return countWays(1) + countWays(0);

and

For countWays(1):

return countWays(0) + countWays(-1)

countWays(0) returns 1, b/c n == 0

countWays(-1) returns 0, b/c n < 0

Completely split down:

countWays(1) returns 1, because it splits down into countWays(0) and countWays(-1) which just turns into 1 + 0 which = 1

countWays(0) returns 1, because n == 0, so it just returns 1

countWays(2) returns 2, because it is combining countWays(1) and countWays(0) which both return 1

Now all thats left is the countWays(1) from before, which returns 1 again

2+1 = 3

hopefully this makes sense because its kinda confusing but i think i found a good way to write it down

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 int countWaysVariableSteps(int n, int[] steps) {

    // Base case: If n == 0, return 1 (one way to stay where you are).
    if (n == 0) {
        return 1;
    }   

    // Base case: If n < 0, return 0 (no valid ways).
    if (n < 0) { 
        return 0;
    }

    int numOfWays = 0;
    for(int i = 0; i < steps.length; i++) {
        numOfWays += countWaysVariableSteps(n - steps[i], steps);
    }

    return numOfWays;
}


int[] steps = {1, 3, 5};
countWaysVariableSteps(5, steps) // returns 5

MC

A. 1728

B. 104

C. 48

D. 248832

E. 144

Walkthrough:

equation(8) splits down into:

equation(6) * equation(7)

which splits down into:

equation(6):

equation(4) * equation(5)

equation(7):

equation(6) * equation(5)

equation 6 returns 144

becuase we know equation 6 returns 144, and equation 5 returns 12,

we can just multiply using what we know

144 * (144 * 12) = 248832 = D.

A. tHISISMYFAVORITEyAYFORPROGRAMMING

B. tHIS IS MYFAVORITE

C. ThIs iS mY fAvOriTe: YaY fOr PrOgRaMmIng!!!

D. tHIS IS MY FAVORITE: yAY FOR PROGRAMMING!!!

E. ThIs iS mY fAvOriTe

Walkthrough:

‘T’ → ‘t’, ‘h’ → ‘H’, ‘i’ → ‘I’, ‘s’ → ‘S’, ‘ ‘ → skip.

‘i’ → ‘I’, ‘s’ → ‘S’, ‘ ‘ → skip.

‘m’ → ‘M’, ‘y’ → ‘Y’, ‘ ‘ → skip.

‘f’ → ‘F’, ‘a’ → ‘A’, ‘v’ → ‘V’, ‘o’ → ‘O’, ‘r’ → ‘R’, ‘i’ → ‘I’, ‘t’ → ‘T’, ‘e’ → ‘E’.

’:’ → skip, ‘ ‘ → skip.

‘Y’ → ‘y’, ‘a’ → ‘A’, ‘y’ → ‘Y’, ‘ ‘ → skip.

‘f’ → ‘F’, ‘o’ → ‘O’, ‘r’ → ‘R’, ‘ ‘ → skip.

‘p’ → ‘P’, ‘r’ → ‘R’, ‘o’ → ‘O’, ‘g’ → ‘G’, ‘r’ → ‘R’, ‘a’ → ‘A’, ‘m’ → ‘M’, ‘m’ → ‘M’, ‘i’ → ‘I’, ‘n’ → ‘N’, ‘g’ → ‘G’.

’!’ → skip.

all in all: tHISISMYFAVORITEyAYFORPROGRAMMING

A. tHISISMYFAVORITEyAYFORPROGRAMMING

What is the base case in a recursive function?

A. The first function call in a recursive chain. B. A condition that stops the recursion by returning a value. C. A recursive call that reduces the problem size. D. A function that calls itself indefinitely.

B. A condition that stops the recursion by returning a value.

The base case in a recursive function is used to stop the recursion by returning some value. For example, one base case in A of the frq we did was if (n==0). If n was 0, the function would return 1, and cease its recursion because a value was returned.