递归算法转换为非递归算法

递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。

直接转换法

直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。

尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。对于尾递归形式的递归算法，可以利用循环结构来替代。

单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。对于单向递归，可以设置一些变量保存中间结构，将递归结构用循环结构来替代。

 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


//斐波那契数列
//递归
int f(int n)
{
    if (n= =1 | | n= =0) return 1;
　　    else return f(n-1)+f(n-2);
}

//非递归
int f(int n)
{
　　int i, s;
      if(n<0)
          return -1;
      else if(n<3)
          return 1;
　　int s1=1, s2=1;
　　for (i=3; i <n; i++)
     {
　　     s=s1+s2;
　　     s2=s1; // 保存f(n-2)的值
　　     s1=s; //保存f(n-1)的值
　　}
　　return s;
}

基于栈结构的间接转换

通用的变换规则如下：假设template P(p1, p2, …,pm)是一个递归过程或函数（省略参数类型说明），其中p1, … , pm为参数，并设过程中有n个局部变量q1, …, qn和t个递归调用本过程P的语句。

(1) 在P中增设工作栈S，以存放当前层工作记录。每个工作记录包含m+n+2个数据项，其说明如下。

1
2
3
4
5
6
7


struct levelstr
{   int p0; // 返回语句标号
    ParaType p；    // p用来保存返回值, 类型与递归过程返回值类型ParaType一致
    // 若递归过程为void, 则此项无意义
    ParaType p1, ..., pm;   // 按原类型定义
    ParaType q1, ..., qn;   // 按原类型定义
} s；

(2) 在P中设置t+2个语句标号：<标号0＞, <标号1＞, …, <标号t+1＞。其中，<标号0＞设在过程体中第一个可执行的语句上，<标号t+1＞设在过程体结束处之前，其余t个标号分别设置在t个调用过程语句的返回处。

(3) 在过程体的第一个执行语句（即<标号0＞的语句为过程P的递归入口）之前，增加下列两个语句作为过程P的非递归入口（从调用过程P的主过程进入过程P的入口）：

1
2


Stack<levelstr> s; // 栈初始化
s.push(<标号t+1>, p, p1, ..., pm, q1, ..., qn); // 当前参量进栈

(4) 假设过程体中第I(i＝1, …, t)个递归调用语句为P(a1, a2, …, am)，其中，ai(i＝1, …, m)为实参。则用下列3个语句替换它。

1
2
3


S.push(<标号i>, a1, ..., am);   // 调用实参进栈
goto <标号0>;   // 转向递归入口处
<标号i>：s.pop( );  // 退栈操作

由于goto语句不能转向一个语句的内部，因此，如果某个递归调用语句包含在另一个语句的内部，则应加以适当处理使所有的语句标号只出现在第一层。

如下列语句组:

while(条件w)LINESw;
LINES;（其中LINESw为第k个递归调用语句）

可改为：

<标号w1>：if(条件w){ s.push(...)； goto <标号0>;}
        else goto <标号w2>
<标号k>： s.pop(); goto <标号w1>;
<标号w2>： LINES; ...

(5) 在过程体中所有递归出口处增加语句。

1
2


s.peek().p = ...； // 若递归过程有返回值，执行此赋值语句
goto s.peek().p0； // 转向栈顶的返回语句标号处

此goto语句的正规写法为：

1
2
3
4
5
6
7


switch(s.peek( ). p0)
{
    case <标号0>:goto <标号0>; break;
    case <标号1>:goto <标号1>; break;
                 ...
    case <标号t+1>:goto <标号t+1>; break;
}

(6) 标号为t+1的语句是增添的实现函数值出栈操作的语句，作为过程P的非递归出口（即返回调用该递归过程的主过程）。

1
2
3
4


<标号t+1>: temp = s.peek().p； // temp为临时变量, 保存返回值
                   // 如递归无返回值, 此语句和下面的return语句可以省略
s.pop();
retutn temp；

(7) 切记实现参量“当前层化”，过程体中出现的所有参变量和局部变量均以栈顶工作记录中相应的数据项代替。

(8) 若算法中有复合递归调用的语句，则应增设局部变量消除复合调用，即，将形如f(…, f(…), …);的语句改写为<局部变量＞：f(…);…f(…, <局部变量＞,…);的形式。

(9) 经过上述变换规则得到的不含递归的算法尚需进行最后一步变换，即简化不必要的操作，如消去冗余进栈的内容等，并画出相应的流程图，从流程图中找出各循环的循环体和循环条件，从而消去goto语句，得到结构清晰的非递归算法。

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


//汉诺塔递归
void Hanoi(int n，char x，y，z)
{
    if(n == 1) move(x,1,z); // 将编号为1的盘子从x移到z
    else
    {
        Hanoi(n-1,x,z,y);
        Move(x,n,z);
        Hanoi(n-1,y,x,z);
    }
}

//机械转换
void Hanoi(int n, char x, y, z)
{
    struct levelstr
    {
        int adr, ptrn; char xp, yp, zp；
    } *s, currentp;
    s= new Stack(m*m-1);    // m*m-1是栈的初始化大小
    s.push(3, n, x, y, z);
    0:currentp = s.peek();  // 局部变量currentp用来保存栈顶元素
        if(currentp.prtn == 1){
          move(currentp.xp, 1, currentp.Zp);
          goto currentp.adr;
        }
        s.push(1, currentp.ptrn-1, currentp.xp,
              currentp.zp, cutrretnp.Yp);
        goto 0;
    1:s.pop();
        currentp = s.peek();
        move(currentp.Xp,currentp.Ptrn, currentp.zp);
        s.push(2, currentp.ptrn –1, currentp.yp,
              currentp.xp, currentp. zp);
        goto 0;
    2:s.pop();
        currentp = s.peek();
        goto currentp.adr;
    3:s.pop();
}

//优化，去goto
void hanoi2(int n, char x, y, z)
{
    struct levelstr
    {
        int ptrn; char xp, yp, zp;
    } s[arrmax];
    int top; char temp; top = 0;
    s[top] = (n, x, y, z); // 栈初始化
    while(!((top==0)&&(s[top].ptrn==1)))
    {
        while(s[top].ptrn > 1)
            s[top++] =(s[top].ptrn-1, s[top].xp,
                        s[top].zp, s[top].yp);
        move(s[top].xp, 1, s[top].zp);
        if (top > 0) {
            top--;
            move(s[top].xp, s[top].ptrn, s[top].zp);
            s[top].ptrn--;
            temp = s[top].xp;
            s[top].xp = s[top].Yp;
            s[top].yp = temp;
        }
    }
    move(s[top].xp, 1, s[top].zp);
    top--;
}

文章目录

直接转换法

基于栈结构的间接转换