Consider the following problem: A person is about to climb a staircase of n stairs. Each step she makes can be either a regular-size step that climbs 1 stair, or a big-size step that climbs 2 stairs. In how many di erent ways can she climb the whole set of n steps ? E.g., for climbing 3 stairs she has 3 possible ways: (reg,reg,reg), (reg,big), (big,reg). Note you don't need to explicitly write her steps but only the number of options she has. Write a recursive solution for solving the problem.

Hint: Think about the base cases ; then look at her last step to de ne the smaller instances and transition: it is either reg or big. If it is reg, then she rst has to get to stair n-1; if it is big, she rst needs to get to stair n-2. Does it seam familiar ?

In pseudocode like below and word description

procedure FindMax (A, n) if (n=1) then return Al1 else return max(A[n], FindMax (A, n - 1))