算法基础算法

递归的机器实现

字数统计: 1.3k字   |   阅读时长: 5分
, ,

摘要: 递归的机器实现，递归转非递归

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 递归 中，我们讨论了与递归的相关的问题，并给出了题目列表。基于递归的两个最典型的算法是回溯和分治。

对于回溯，在文章 枚举 中，我们通过若干 leetcode 的题目总结了多项式、指数、排列、组合型枚举。

对于分治，在文章 分治 中，我们系统学习了分治算法，了解了分治的思想和流程，以及研究分治算法时间复杂度的主定理，然后用分治算法解决了几道 leetcode 的题目，最后提到了分治与减治和搜索的区别和联系。在文章 减治法 中，我们学习了跟分治很像但是有点区别的减治法，同样放了 leetcode 的很多题目。

本文我们看一下递归在计算机中是如何实现的，然后以组合型枚举为例，看看如何将递归程序转换为非递归的，这个例子的代码可以作为模板使用。主要参考资料为《算法竞赛进阶指南》0x02。

递归的机器实现

要谈递归在计算机中是如何实现的，首先要从函数调用说起。

对于一台典型的计算机采用堆栈结构实现函数调用，它在汇编语言中，把函数所需的第 k 个、第 k - 1 个、…、第 1 个参数依次入栈，然后执行 call(address) 指令。该指令把返回地址(当前语句下一条语句的地址)入栈，然后跳转到 address 位置的语句。函数返回时，它执行 ret 指令，该指令把返回地址出栈，并跳转到该地址继续执行。

对于函数中定义的 C++ 局部变量，在每次执行 call 和 ret 指令时，也会在栈中相应地保存与复原，通过 new 和 malloc 动态分配的空间则保存在另一块称为堆的结构中。栈指针、返回值、局部的运算会借助 CPU 的寄存器完成。

综上我们可以知道

  1. 局部变量在每层递归中都占有一份空间，声明过多或递归过深会超过栈能存储的范围，造成栈溢出。
  2. 非局部变量对于各层递归都共享同一份空间，需要及时维护、还原现场，以防止在各层递归之间存储和读取的数据互相影响。

根据递归的机器实现，将递归转非递归

了解了递归的及其实现后，我们就可以使用模拟的方法，把递归程序改写为非递归程序。

我们可以用一个数组来模拟栈、使用变量来模拟栈指针和返回值，使用 switch/case 或 goto/label 来模拟语句的跳转。

例子: 非递归实现组合型枚举

从 1 ∼ n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

针对这种组合型的枚举，递归代码如下：

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
#include <iostream>
#include <vector>

using namespace std;

vector<int> vec; // 被选择的
int n, m;

void dfs(int i)
{
    if(vec.size() == m)
    {
        // 问题边界
        for(int x: vec)
            cout << x << " ";
        cout << endl;
        return;
    }
    if(vec.size() + n - i + 1 < m)
        return;
    // 选 i
    vec.push_back(i); // 记录 i 已被选择
    dfs(i + 1);
    vec.pop_back(); // 回溯前，还原现场
    // 不选 i
    dfs(i + 1);
}

int main()
{
    cin >> n >> m;
    dfs(1);
}

下面用模拟递归的方法改写非递归版本。

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
69
70
71
72
73
74
75
#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;
int stack[N];
int top = 0, address = 0;

int n, m;
vector<int> vec; // 被选择的

void call(int ret_addr)
{
    // 模拟计算机汇编指令 call
    // i 是参数, ret_addr 是函数返回时的地址
    int old_top = top - 1;
    stack[++top] = ret_addr; // 返回地址标号
    stack[++top] = old_top; // 在栈顶记录以前的 top 值
}

int ret()
{
    // 模拟计算机汇编指令 ret
    int ret_addr = stack[top - 1];
    top = stack[top]; // 恢复以前的 top 值
    return ret_addr;
}

void print()
{
    for(int i = 0; i < vec.size(); ++i)
        printf("%d ", vec[i]);
    puts("");
}

int main()
{
    cin >> n >> m;

    stack[++top] = 1; // 参数 1
    call(0); // dfs(1)
    while(top)
    {
        int i = stack[top - 2]; // 获取参数
        switch(address)
        {
            case 0:
                if(vec.size() == m)
                {
                    print();
                    address = ret(); // return
                    continue;
                }
                if(vec.size() + (n - i + 1) < m)
                {
                    address = ret(); // return
                    continue;
                }
                vec.push_back(i);
                stack[++top] = i + 1; // 参数 i + 1
                call(1); // 相当于 dfs(i + 1)，返回后会从 case1 继续
                address = 0;
                continue; // 返回到 while 循环开头，相当于开始新的递归
            case 1:
                vec.pop_back();
                stack[++top] = i + 1; // 参数 i + 1
                call(2); // 相当于 dfs(i + 1)，返回后会从 case2 继续
                address = 0;
                continue; // 回到 while 循环开头，相当于开始新的递归
            case 2:
                address = ret(); // 相当于原 dfs 函数结尾，执行 return
        }
    }
}
Share