AdvancedNumeric answer

Climbing a staircase · Part 3 of 3

You climb a staircase one move at a time. Each move climbs a number of steps from an allowed set, and two climbs differ if their sequences of moves differ, so 1 then 2 and 2 then 1 count separately.

Back to moves of 1 or 2. An uncached recursive `ways(n)` returns 1 when `n <= 1` and otherwise returns `ways(n - 1) + ways(n - 2)`. How many calls, the first included, does `ways(20)` make?

Answer with a number. Fractions, powers and expressions like 23/6 or C(52,5) are read correctly in practice.

The worked solution is in Premium

The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.

Start the 7-day free trial Practise it with Premium

Learn the method

Complexity: reading it off, and deriving it

Back to moves of 1 or 2. An uncached recursive ways(n) returns 1 when n <= 1 and otherwise returns ways(n - 1) + ways(n - 2). How many calls, the first included, does ways(20) make?

More data structures and algorithms questions

Back to moves of 1 or 2. An uncached recursive `ways(n)` returns 1 when `n <= 1` and otherwise returns `ways(n - 1) + ways(n - 2)`. How many calls, the first included, does `ways(20)` make?