Akm函数递归与非递归解法.pdf

Akm函数递归与⾮递归解法 如下是Akm函数的递归算法，根据Akm函数的递归定义就可以得出，请参考 int AkmRecur(int m, int n) { if (m == 0) return n + 1; else if (n == 0) return AkmRecur(m - 1, 1); else AkmRecur(m - 1, AkmRecur(m, n - 1)); } ⾮递归算法没有递归算法简单，你先计算⼀下Akm(2,1)，多计算⼏遍（我建议2遍，并在计算的过程中，分析⼀下计算过程有什么规 律）。 如果你计算完了，就可以看下⾯的分析了（请不要懒，应为计算的量是⽐较⼩的） ①计算的过程中，我们发现有这样的变化 akm(2,1)=akm[1,akm(2,0)]（你可能注意到这是第⼀步） 然后如果要继续算下去，那么我们要计算出 akm(2,0) 这个Akm函数的值。所以第⼀步思考，如何让计算机懂得计算akm[1,akm(2,0)]⾥⾯的akm(2,0)⽽不是看到akm[1,akm(2,0)]就傻掉了 （死板的计算机如果只懂的计算akm(2,0)这种形式的话）。如果仔细观察⼀下，你会发现右边的Akm函数多了⼀个数字0，或者说数字多 了⼀个（左边只有2和0两个数字，右边有1，2和0三个数字），所以可以通过这个特点设置⼀个tag标志，-1表⽰左边的形式，如果⾮-1的 话，那么就是右边的形式，计算机可以通过观察tag来区别计算左边还是右边（如果你觉得不太懂，可以等下看算法，算法很清晰，⽐我这 ⾥啰嗦要好） ②如果计算得到了值（Akm中，当m=0的时候，函数的值确定了，为n+1），如何返回？如果你计算了，请观察⼀下过程，发现你要带回 的地⽅，恰好是形式转变的地⽅（形如akm(2,0)=akm[1,akm(2,0)]的地⽅），所以通过这个特点，可以赋值在右边式⼦的第⼆个数（把 带回的值赋值给右边式⼦的第⼆个数，你不也是这样带回的吗？），⽽要⼀直略过的地⽅（就是得到的值要带回，离恰好形式转变的式⼦中 间应该有不少等式），可以发现都是akm(x,y)的形式，⽽且其tag值应为-1（如果你觉得听得很模糊，没关系，等下看下算法就全懂了） ③还有⼀点，就是如何带回结果的问题，我不善于表达，请直达下⾯的代码吧。 代码如下 int AkmNRecur(int m, int n) { SeqStack S; InitStack(&S); AkmElem e; e.m = m, e.n = n, e.k = -1;//⼀开始的m,n压⼊栈中 Push(&S, e); while (1) { AkmElem v, x; GetTop(&S, &v); if (v.k != -1) { v.m = v.n; v.n = v.k;//-1表⽰是akm(x,y)形式，如果不是这个形式，则k应该等于⼀个正整数 } if (v.m == 0)//复杂度最⾼的情况 { int value; value = v.n + 1;//计算结果 do { Pop(&S); if (IsEmpty(&S))//如果连续出栈导致栈空，那么表⽰返回值就是akm函数的结果 return value; else GetTop(&S, &x); } while (x.k == -1); Pop(&S); x.k = -1; x.n = value; Push(&S, x);//这⾥表⽰计算机完成对akm[1,akm(2,0)]形式中akm(2,0)的计算了，现在应该是akm(1,3)这种形式 } else if (v.n == 0)//如果是这种情况，那么需要⼊栈，应为还不知道结果，要继续运算 { x.k = -1; x.m = v.m - 1; x.n = 1; Push(&S, x); } else//这种情况同v.n==0分析 { x.m = v.m - 1;