There are a total of N steps in a stair. You can either take one or two steps at a time. Write efficient code to print all possible ways of climbing.

There are a total of N steps in a stair. You can either take one or two steps at a time. Write efficient code to print all possible ways of climbing.

Use recursion, each time we have two choices, taking one step or taking two steps, so we have Fibonacci number ways to reach final

int foo(int n)
{
if(n<0) return 0;
if(n==0) return 1;
return f(n-1)+f(n-2);
}
//s(n)=s(n-1)+s(n-2)
//s(1)=1;s(2)=2