栈的应用4——递归函数的非递归形式（主讲阿克曼函数的非递归形式）_阿克曼函数非递归讲解

递归

函数自己调用自己
如求阶乘函数：

int jiecheng(int n)
{
	if(n==0)
		return 1;
	if(n==1)
		return 1;
	else 
		return n*jiecheng(n-1);
}
1
2
3
4
5
6
7
8
9

脑补一下如果在主函数里面调用这个函数输入5的话，函数返回5*jiecheng（4），所以这个函数还要继续调用下去，这就是自己调用自己的函数——递归函数。

举例说明：汉诺塔、阿克曼函数、阶乘、斐波那契数列

和栈的联系

递归函数最后要返回 5！，但是他最开始只能知道答案是5乘一个函数的返回值，那么还要继续使用这个函数，但是5这个结果还不能扔了，所以就只能先将这个数据放起来，这时就用到了栈。

汉诺塔

#include <iostream>

using namespace std;

void move(int n,char A,char B,char C);

int step;

int main()
{
    int n;
    cout<<"input the number:"<<endl;
    cin>>n;
    move(n,'A','B','C');
    return 0;
}

void move(int n,char A,char B,char C)
{
    if(n==1)
    {
        step++;
        cout<<"["<<step<<"]move 1# from "<<A<<" to "<<C<<endl;
    }
    else
    {
        move(n-1,A,C,B);
        cout<<"["<<step<<"]move "<<n<<"# from "<<A<<" to "<<B<<endl;
        step++;
        move(n-1,B,A,C);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

（楼上的陈年老代码也不知道是啥时候的，当时也是借鉴了别人的才整出来的）

阿克曼函数的递归形式与非递归形式

Ackermann(a,b)函数定义如下：
若a=0，返回b+1。
若a>0且b=0，返回Ackermann(a-1,1)。
若a>0且b>0，返回Ackermann(a-1,Ackermann(a,b-1))。

递归形式

int digui(int a,int b)//递归函数
{
    if(a==0)//分别对应三种情况
    {
        return b+1;
    }
    else if(b==0)
    {
        return digui(a-1,1);
    }
    else
    {
        return digui(a-1,digui(a,b-1));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归的没啥好说，非递归稍提一下。

非递归

思路
只有第一种能告诉你答案是多少，所以都要最后归到第一类。
给你一对ab，按定义来，对应着不同的方式，第一第二不用说，第三种需要先记录当前的a，然后进入下一对ab的阿克曼函数计算。
在最后不需要新的函数时（也就是a为0了），这个时候能算出来一个值，到了最底层，这个时候就要返回了，
返回上一个函数或者是直接输出，在之前你是通过二三类才得到的答案，
但二类不改变当前的值，不管；
退回到第三类的时候，就是到了上一个函数，此时a、b的值都是定值了，再次计算就行了。
直到最后到达了初始，结束循环，返回结果。

很晕，那么就看一个例子（2，1）吧

1. 对应第三种，那就先计算（2.0）
2. 对应第二种，（2，0）和（1，1）相同；
3. 需要计算（1，1），但要有（1，0）；
4. （1，0）和（0，1）相同，而（0，1）我们知道，所以就可以计算（1，1）了，（1，1）和（0，2）相同
5. （0，2）也知道，那就继续返回，直到我们得到了（2，1）

代码分析
阿克曼函数有两个自变量，需要分别处理，所以创建两个栈分别处理。

因为原来的递归函数分为三种，所以在非递归里面思路相同，也要分三种情况分别讨论。

1. 如果是第一种情况，直接退出循环，返回b+1；
2. 如果是第二种情况，将ab的值处理后可以先压入栈内等候发落。
3. 第三种情况比较麻烦，因为需要调用另外一个阿克曼函数，所以a还是按定义存入 a-1，但是这个时候不知道b是多少啊。所以存一个-1，占位并作为标识。而此时的a仍为a，b减一（是为了对应后面的阿克曼函数）

此时是递归到当前阿克曼函数最底层的过程，当a=0时结束，然后就是反过来计算的过程。

1. 首先是将b加一，因为此时符合第一条，需要先进行操作。
2. 要知道，第二种情况是对输出结果没有影响的，所以完全可以抛开不看，而第一种已经处理完了，第三种有b=-1的特殊标记，所以在栈非空和没有标识的情况下，直接将内容弹出栈就行了。
3. 在将不改变数值的第二类输出了之后，如果栈非空，那就是第三种情况了，将上层函数对应的ab找到，带入继续上述过程
4. 退出条件是栈空。

代码：

int xunhuan(int a,int b)
{
    struct link* heada=(struct link*)malloc(sizeof(struct link)),* headb=(struct link*)malloc(sizeof(struct link));//两个栈，分别存入ab
    heada->next=NULL;
    headb->next=NULL;
    heada=input(heada,a);//开始先将ab压入栈
    headb=input(headb,b);
    while(heada->next)//栈非空（两个栈应当是同时空，写一个即可）
    {
        while(a!=0)//a=0可直接求出来，跳出循环的条件
        {
            if(b==0)//第二种情况
            {
                a-=1;
                b=1;
                input(heada,a);
                input(headb,b);//再次压入栈
            }
            else//最后一种麻烦的
            {
                b-=1;
                input(heada,a-1);
                input(headb,-1);//特殊标识
            }
        }
        b++;//a=0的情况
        while(heada->next&&headb->next->data!=-1)//将没有用的输出
        {
            output(heada);
            output(headb);
        }
        if(heada->next)
        {
            a=heada->next->data-1;
            output(headb);
            input(headb,b);//将b改为我们已经直到了的值，带入上层函数计算。
        }
    }//外层while结束
    return b;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

另附（2，1）栈的变化

另外说明一下，如果是递归的方式计算该函数，看看上面的图就知道很麻烦，虽然数值不大，但是（4，5）就可能让人崩溃，所以测试的时候建议选择小一点的例子。