Basics of Recursive Programming (recitation)

932 views

Count Stairs

You want to go up a flight of stairs that has steps. You can either take or steps each time. How many different ways can you go up this flight of stairs? Write a function count_stair that solves this problem for you. Assume is positive.

Before we start, what’s the base case for this question?

What is the simplest input?

Could it be when there is one stair? or two stairs? or no stairs?

After you’ve thought of a base case, think about a recursive call with a smaller argument that approaches the base case.

Need a hint?

What do count_stair(n - 1) and count_stair(n - 2) represent?

Implement a recursive solution for count_stair:

Implement count_stair
// { autofold
package com.yourself;
public class CountStair {
// }
// Goal: count how many different ways one can go up a flight of stairs.
// Constraint: you can take 1 or 2 steps each time.
// Parameter: n is the number of stairs.
// REQUIRES: n >= 0
// EFFECTS: returns the count of different ways one can go up a flight of stairs.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Consider a special version of the count_stair problem, where instead of taking or steps, we are able to take up to and including steps at a time.

Write a function count_k that figures out the number of paths for this scenario. Assume and are positive.

Implement count_k
// { autofold
package com.yourself;
public class CountK {
// }
// Goal: count how many different ways one can go up a flight of stairs.
// Constraint: you can up to and including k steps each time.
// Parameter: n is the number of stairs, k is the number of steps you may take.
// REQUIRES: n >= 0 && k > 0
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX