软件设计师考试冲刺例题解析：递归算法

例题20

递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解。

下面举一个经典的递归算法例子——斐波那契数列问题来说明这一过程。

斐波那契数列为：0，1，1，2，3，…，即

fib(0)0;

fib(1)1;

fib(n)fib(n1)fib(n2)（当n1时）

写成递归函数有：

int fib(int n)

{if(n==0)return 0;

if(n==1)return 1;

if(n1)return fib(n1)fib(n2);

}

这个例子的递推过程为：求解fib(n)，把它推到求解fib(n1)和fib(n2)。也就是说，为计算fib(n)，必须先计算fib(n1)和fib(n2)，而计算fib(n1)和fib(n2)，又必须先计算fib(n3)和fib(n4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib(n)中，当n为1和0的情况。

回归过程为：得到fib(1)和fib(0)后，返回得到fib(2)的结果，……在得到了fib(n1)和fib(n2)的结果后，返回得到fib(n)的结果。

例题20答案

（20）B