Loading [MathJax]/jax/output/CommonHTML/jax.js
Back
Close

Basics of Recursive Programming (recitation)

madooei
932 views

Count Stairs

You want to go up a flight of stairs that has n steps. You can either take 1 or 2 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 n 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 1 or 2 steps, we are able to take up to and including k steps at a time.

Write a function count_k that figures out the number of paths for this scenario. Assume n and k 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
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants