第5章递归与广义表 计算akm(2,1)的递归调用树如图所示: =akm(2,0) a(3)am=5 akm(1 akm =3 =akm(1,2)|akm(0,4)=5 y=2 v=am(1,0)|am0,2)=3 用到一个栈记忆每次递归调用时的实参值,每个结点两个域{vm,Ⅶm。对以上实例,栈 的变化如下: V vn 1n vn 1 1 vn 改akm(m-1,1) 改akm(m-1,1)y=n+1=2改akmm-1,y)改akm(m-1,) 翻誧蚩 改akm(m-1,1)y=n+1=2改akmn(m-1,1)改akmm-1,y)改akm(m-1,)栈空,返回v=5 =n+1=3v=n+1=4v=n+1=5 相应算法如下 #include <iostream. h> include“ stack h #define max Size 3500; ed tack<node>st( maxSize ) node wvm=m; wvn=n; st Push(w); while( st GetTop().vm >0)t 川计算akm(m-1,akm(m,n-1))第 5 章 递归与广义表 55 } 计算 akm(2, 1)的递归调用树如图所示： 用到一个栈记忆每次递归调用时的实参值，每个结点两个域{vm, vn}。对以上实例，栈 的变化如下： 相应算法如下 #include <iostream.h> #include “stack.h” #define maxSize 3500; unsigned akm ( unsigned m, unsigned n ) { struct node { unsigned vm, vn; } stack<node> st ( maxSize ); node w; unsigned v; w.vm = m; w.vn = n; st.Push (w); do { while ( st.GetTop( ).vm > 0 ) { //计算 akm(m-1, akm(m, n-1) ) akm(2, 1) v =akm(2, 0) akm(1, 1) v =akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(1, 3) v = akm(1, 2) v = akm(1, 1) v = akm(1, 0) akm(0, 1) = 2 akm(0, 2) = 3 akm(0, 3) = 4 akm(0, 4) = 5 v = 2 v = 2 v = 3 v = 4 v = 3 akm = 5 akm = 5 akm = 3 2 1 2 1 2 1 2 1 2 1 1 3 2 0 1 1 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) 改 akm(m-1,1) v = n+1= 2 改 akm(m-1,v) 改 akm(m-1,v) v = n+1 = 3 vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn vm vn 1 3 1 3 1 3 1 3 0 4 1 2 1 2 1 2 0 3 1 1 1 1 0 2 1 0 0 1 改 akm(m-1,1) v = n+1 = 2 改 akm(m-1,v) 改 akm(m-1,v) 改 akm(m-1,v) 栈空, 返回 v = 5 v = n+1 = 3 v = n+1 = 4 v = n+1 = 5