Question

关于C语言的一个递归问题，求大神解答

一段楼梯有N阶，可以一次上1阶，也可以一次上2阶，用递归函数调用实现，计算多少种走法。则递归公式和边界条件是（ ）

A.
f[n]=f[n-1]+f[n-2] 边界条件 当n=1 f[1]=0, 当n =2 f[2]=1

B.
f[n]=f[n-1]+f[n-2] 边界条件 当n=1 f[1]=1, 当n =2 f[2]=2

C.
f[n]=f[n-1] 边界条件 当n=1 f[1]=1

D.
f[n]= f[n-2] 边界条件 当n=2 f[2]=1

为什么选B？

Answer 1

当N=1时只有一种走法。即1
N=2时有两种走法，可一次两节，或两次一节。
N=3时有三种
N=4时有五种
规律就出来了，即f[n]=f[n-1]+f[n-2] 。
当n=1 f[1]=1, 当n =2 f[2]=2