例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.

　　设n阶台阶的走法数为f(n)

　　显然有

　　1  n=1

　　f(n)={2  n=2

　　f(n-1)+f(n-2)  n>2

　　可编程序如下：

　　program louti;

　　var n:integer;

　　function f(x:integer):integer;

　　begin

　　if x=1 then f:=1 else

　　if x=2 then f:=2 else f:=f(x-1)+f(x-2);

　　end;

　　begin

　　write('n=');read(n);

　　writeln('f(',n,')=',f(n))

　　end.

　　2.2 如何设计递归算法

　　1.确定递归公式

　　2.确定边界(终了)条件

　　练习:

　　用递归的方法完成下列问题

　　1.求数组中的最大数

　　2.1+2+3+...+n

　　3.求n个整数的积

　　4.求n个整数的平均值

　　5.求n个自然数的最大公约数与最小公倍数

　　6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?

　　7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.