递归过程改为非递归过程 递归过程简洁、易编、易懂 递归过程效率低,重复计算多 改为非递归过程的目的是提高效率 单向递归和尾递归可直接用迭代实 现其非递归过程 其他情形必须借助栈实现非递归过 程
递归过程改为非递归过程 ◼ 递归过程简洁、易编、易懂 ◼ 递归过程效率低，重复计算多 ◼ 改为非递归过程的目的是提高效率 ◼ 单向递归和尾递归可直接用迭代实 现其非递归过程 ◼ 其他情形必须借助栈实现非递归过 程
计算斐波那契数列的函数Fib(n)的定义 n=0.1 Fib(n) Fib(n-1)+Fib(n-2), n>1 如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5 求解斐波那契数列的递归算法 long Fib( longni if(n<=1)return n; else return Fib (n-1)+ Fib(n-2);
计算斐波那契数列的函数Fib(n)的定义 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); } − + − = = Fib(n 1) Fib(n 2), n 1 n, n 0,1 Fib(n ) 如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5
Fib(5) Fib(4) Fib(3) Fib(3) Fib(2 Fib(2) Fib(1) Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) Fib(0) 斐浪那契数列的递归调用树 调用次数 NumCall(k)=2*Fib(k+1)-1
调用次数 NumCall(k) = 2*Fib(k+1) - 1。 斐波那契数列的递归调用树 Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(5)
Fib(4) Fib(3) Fib(2 Fib(2) Fib(1) Fib(1) Fib(o 0/ Fib(1) Fib(O) 栈结点ntg tag=1,向左递归;tag=2,向右递归
Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) 栈结点 n tag tag = 1, 向左递归；tag = 2, 向右递归
Q Fib(4 5 Fib(3) Fib(2) 3 Fib(2) Fib(1)Fib(1) Fib(0 Fib(1) Fib(0 82122 s31631631632 941(941941941941(42 22n=04 4n=18 sum=0+1n=2-2sum=1+0n=3-2sum=1+1n=4-2
Fib(1) Fib(0) Fib(2) Fib(1) Fib(0) Fib(2) Fib(1) Fib(3) Fib(4) 2 1 3 1 4 1 n=1 sum=0+1 2 2 3 1 4 1 n=2-2 3 1 4 1 n=0 sum=1+0 3 2 4 1 n=3-2 4 1 n=1 sum=1+1 4 2 n=4-2