如何利用栈和循环替代递归

发表于 | 更新于 | 评论数： | 阅读次数：

递归更加利于理解，因此某些情况下我们更喜欢使用递归（比如归并排序、或者树的操作），但是随着递归深度不断加深，就可能出现栈溢出，很多大神可能都已经知道如何通过堆栈和循环来避免栈溢出，但是，我觉得提供一种简单、通用的方法来替换递归，对于新手来说是非常棒的想法。

递归和循环的优缺点

递归：

  • 优点：便于阅读和理解算法；
  • 缺点：可能引起栈溢出；

循环：

  • 优点：能够避免栈溢出；效率通常要比递归更好一些；
  • 缺点：不利于理解代码，不易维护；

替换递归的 10 个规则

下面介绍的几种规则，是针对通用的递归转换方法，而在实际的使用中，对于简单的递归来说，可能只需要其中一部分就可以解决问题，所以在阅读过程中，需要着重理解每个原则解决哪些问题。

规则 01

递归和循环根本的差异在于，递归调用借助线程调用栈，来存储参数、局部变量等信息，因此转换时需要我们完成这部分工作，通过定义一个结构体SnapShot，来存储递归过程中的所有数据，以及阶段信息，总结结构体包括内容如下：

  • 当递归调用时值发生变化的参数，引用类型参数时不需要添加到结构体中，比如下面例子中，参数 n 需要添加，而引用类型 retVal 则不需要；
  • 阶段标记（主要用来解决递归中的分支问题，后面会详细介绍）；
  • 一些局部变量（递归调用返回后需要使用的局部变量）；
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
int SomeFunc(int n,int &retIdx)
{
    if(n > 0)
    {
        int test = SomeFunc(n-1,retIdx);
        test--;
        return test;
    }

    printf("some content %d",retIdx);
    return 0;
}

// 规则 1
struct SnapShot
{
    int n;          // 输入参数
    int test;       // 局部变量，在递归调用之后需要使用
    int stage;      // 因为递归之后还有需要执行的代码，就需要对代码不同过程进行标记
};

// 将递归转换为循环
// （根据后续规则，不断进行完善）
int SomeFuncLoop(int n,int &retIdx)
{
}

规则 02

在循环模拟方法最开始，创建一个局部变量，该变量用于存储递归调用的返回值。

  • 该值等同于递归中的返回值，如果需要用到返回值，直接使用该变量替代；
  • 如果递归函数返回值是 void 类型，则不需要使用局部变量；
  • 使用递归函数默认返回值，来初始化该局部变量；
1
2
3
4
5
6
7
8
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    return retVal;
}

规则 03

创建一个SnapShot类型的堆栈，通过这个堆栈来模拟线程调用栈，继续上面的例子。

1
2
3
4
5
6
7
8
9
10
11
12
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    // 规则 3
    std::stack<SnapShot>  snapshotStack;

    // 规则 2
    return retVal;
}

规则 04

  1. 创建一个SnapShot实例对象，并且根据循环的输入参数以及状态其实值，初始化该实例；
  2. 然后将该实例添加到创建的堆栈中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    // 规则 3
    std::stack<SnapShot>  snapshotStack;

    // 规则 4
    SnapShot currentSnapStack;
    currentSnapStack.n = n;
    currentSnapStack.test = 0;
    currentSnapStack.stage = 0;

    snapshotStack.push(currentSnapStack);

    // 规则 2
    return retVal;
}

规则 05

  1. 创建一个 while 循环，循环条件为 snapshotStack 不为空；
  2. 每次循环时，从 snapshotStack 取出栈顶元素。
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
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    // 规则 3
    std::stack<SnapShot>  snapshotStack;

    // 规则 4
    SnapShot currentSnapStack;
    currentSnapStack.n = n;
    currentSnapStack.test = 0;
    currentSnapStack.stage = 0;

    snapshotStack.push(currentSnapStack);

    // 规则 5
    while(!snapshotStack.empty())
    {
        currentSnapStack = snapshotStack.top();
        snapshotStack.pop();

        // ...
    }

    // 规则 2
    return retVal;
}

规则 06

前面提到过 SnapShot 结构中有一个 stage 变量，用来存储递归的各个阶段，那么如何划分阶段，每个阶段内容是什么，后续将会一一解释，下面这一规则说明了，如何对递归进行阶段划分。

  1. 以递归调用为分界点，将整个过程分为两部分（针对只有一个递归调用的情况），第一部分为调用前，第二部分表示递归调用后的代码；
  2. 如果一个函数中有两个递归调用，则必须有三个阶段：
    1. 第一阶段 -> 递归调用 -> (上次递归调用返回)第二阶段（第二次递归调用） -> （第二次递归调用返回) -> 第三阶段
  3. 如果一个函数中有三个递归调用，则至少有四个阶段；
  4. 依次类推。
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
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    // 规则 3
    std::stack<SnapShot>  snapshotStack;

    // 规则 4
    SnapShot currentSnapStack;
    currentSnapStack.n = n;
    currentSnapStack.test = 0;
    currentSnapStack.stage = 0;

    snapshotStack.push(currentSnapStack);

    // 规则 5
    while(!snapshotStack.empty())
    {
        currentSnapStack = snapshotStack.top();
        snapshotStack.pop();

        // 规则 6
        switch (currentSnapStack.stage)
        {
        case 0: 
            // 阶段 1，SomeFunc(n-1,retIdx) 之前的内容 
            break;
        case 1:
            // 阶段 2，SomeFunc(n-1,retIdx) 之后的内容
            break;
        }
    }

    // 规则 2
    return retVal;
}

规则 07

  1. 在规则 6 中确定阶段划分之后，需要根据 SnapShot.stage 变量来决定进入哪个 case；
  2. 执行相关的阶段代码；
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
// 将递归转换为循环
int SomeFuncLoop(int n,int &retIdx)
{
    // 规则 2
    int retVal = 0;     // 采用默认返回值来初始化变量

    // 规则 3
    std::stack<SnapShot>  snapshotStack;

    // 规则 4
    SnapShot currentSnapStack;
    currentSnapStack.n = n;
    currentSnapStack.test = 0;
    currentSnapStack.stage = 0;

    snapshotStack.push(currentSnapStack);

    // 规则 5
    while(!snapshotStack.empty())
    {
        currentSnapStack = snapshotStack.top();
        snapshotStack.pop();

        // 规则 6
        switch (currentSnapStack.stage)
        {
        case 0: 
            // 阶段 1，SomeFunc(n-1,retIdx) 之前的内容 
            // 规则 7
            if(currentSnapStack.n > 0)
            {
            }
            break;
        case 1:
            // 阶段 2，SomeFunc(n-1,retIdx) 之后的内容
            // 规则 7
            currentSnapStack.test = retVal;
            currentSnapStack.test -- ;
            break;
        }
    }

    // 规则 2
    return retVal;
}

阶段 2 中我们给 test 进行了赋值，规则 1 中提到，凡是在递归调用之后，需要用到的局部变量，都需要记录到 SnapShot 中，因此这里需要记录到相应结构。
规则 2 中提到，凡是用到返回值的地方，都用声明的局部变量来替代，因此将 retVal 赋值给 test。

规则 08

  1. 如果递归调用存在返回值，将每次循环的结果，记录到之前声明的局部变量中，比如这里的retVal；
  2. 当while循环结束时，该局部变量存储着递归函数的最终结果；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
switch (currentSnapStack.stage)
{
case 0:
    // 阶段 1，SomeFunc(n-1,retIdx) 之前的内容
    // 规则 7
    if(currentSnapStack.n > 0)
    {
    }

    // 规则 8
    retVal = 0;
    break;
case 1:
    // 阶段 2，SomeFunc(n-1,retIdx) 之后的内容
    // 规则 7
    currentSnapStack.test = retVal;
    currentSnapStack.test -- ;

    // 规则 8
    retVal = currentSnapStack.test;
    break;
}

规则 09

如果递归函数中，包含关键字return，在循环中，需要将之转换为 continue：

  • 当递归中返回一个值时，首先根据规则 8,将返回值存储到临时变量（retVal)，然后调用 continue；
  • 大多数情况下，规则 9 是可选的，但是为了避免逻辑错误，最好加上；
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
switch (currentSnapStack.stage)
{
case 0: 
    // 阶段 1，SomeFunc(n-1,retIdx) 之前的内容 
    // 规则 7
    if(currentSnapStack.n > 0)
    {
    }

    // 规则 8
    retVal = 0;
    // 规则 9
    continue;
    break;
case 1:
    // 阶段 2，SomeFunc(n-1,retIdx) 之后的内容
    // 规则 7
    currentSnapStack.test = retVal;
    currentSnapStack.test -- ;

    // 规则 8
    retVal = currentSnapStack.test;
    // 规则 9
    continue;
    break;
}

规则 10

  1. 对于递归调用，需要再循环中，创建一个新的Snapshot 实例对象，初始化该对象的 stage 变量，以及输入参数、局部变量，然后将该实例添加到堆栈中，并且调用continue；
  2. 如果递归调用之后，还有代码需要执行，则需要将 currentSnapStack.stage 设置为相应阶段，并在新的Snapshot 实例添加到堆栈之前，添加到堆栈中；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 阶段 1，SomeFunc(n-1,retIdx) 之前的内容 
// 规则 7
if(currentSnapStack.n > 0)
{
    // 规则 10
    currentSnapStack.stage = 1;             // 因为有后续代码，因此需要将 currentSnapStack 
                                            // 设置后添加到堆栈中
    snapshotStack.push(currentSnapStack);   // 必须在新的 Snapshot 对象添加之前

    SnapShot newSnapshot;
    newSnapshot.n = currentSnapStack.n - 1; // 输入参数设置，就像调用递归时一样 SomeFunc(n-1,retIdx)
    newSnapshot.test = 0;                   // 根据函数默认值返回值，进行初始化
    newSnapshot.stage = 0;                  // 递归调用需要重新开始执行函数，因此 stage 设置为 0

    snapshotStack.push(newSnapshot);
    continue;
}

各类递归示例

示例代码地址

如果你看过这些源码，你会发现，里面包含递归和循环两个版本，其原因简单来说，循环版本是为了避免栈溢出，而递归版本则是为了阅读源码的人理解算法的意思。

总结

我的观点是，当使用 C/C++ 或者 Java 时，必须非常小心的使用递归，避免栈的溢出异常，但是，在许多情况下，递归代码更容易理解，并且更加容易写出来，但缺点是容易造成栈溢出。所以，通过上述方法，将递归转换为循环，并不是为了提高代码可读性，也不是为了提高代码执行效率，而是通过一种简单的方式避免栈溢出。

如前面所说，我更倾向于保存递归和循环两个版本代码，递归版本给人阅读，循环版本给计算机阅读，当你了解了这两种方式的利弊之后，可以选择使用哪种方式编写代码。

最后附上英文原文地址:英文版

以及原作者的个人 GitHub 库，其中包含部分示例：地址