递归算法的执行过程,一般来说,可先后分成(20)两个阶段。

admin2015-06-03  23

问题 递归算法的执行过程,一般来说,可先后分成(20)两个阶段。

选项 A、试探和回归
B、递推和回归
C、试探和返回
D、递推和返回

答案B

解析 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。
    在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解。
    下面举一个经典的递归算法例子——斐波那契数列问题来说明这一过程。
    斐波那契数列为:0,1,1,2,3,…,即
    fib(0)  =0;
    fib(1)  =1;
    fib(n)  =fib(n-1)+fib(n-2)    (当n>1时)
    写成递归函数有:
    Int  fib(int n)
    {    if  (n==0)    return  0;
    if  (n==1)    return  1;
    if  (n>1)    return  fib(n-1)+fib(n-2);
    }
    这个例子的递推过程为:求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib(n)中,当n为1和0的情况。回归过程为:得到fib(1)和fib(0)后,返回得到fib(2)的结果……在得到了fib(n-1) 和fib(n-2)的结果后,返回得到fib(n)的结果。
转载请注明原文地址:https://kaotiyun.com/show/U3RZ777K
0

相关试题推荐
最新回复(0)