递归的机器实现

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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