![](https://csdnimg.cn/release/download_crawler_static/86331096/bg3.jpg)
第 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