Data Structure c++

Suppose a stair way has N steps where N is a positive integer. How many different ways can you up the stair way if, as you up, sometimes you go up one stair step with one step or you go up two stair step with one step.

Suppose the stair way has 3 steps then you can up the stair way

three different ways:

1,1,1 = 3 steps

1,2 = 3 steps

2, 1 = 3 steps

Suppose the stair way has 4 steps then you can up the stair way

five different ways

1,1,1,1 = 4 steps

1,1,2 = 4 steps

1,2,1 = 4 steps

2, 1,1, = 4 steps

2,2 = 4 steps

Write a recursive function to solve the problem.

The function, f, will contain statements that will look like,

...

return f(N-1) + f(N-2)

Write a program to test the function with many, different values of N.