[科技知识] 所有递归都可以改写成循环吗？

天天财汇购物网址万年历小说 | 三峰软件小游戏视频

TxT小说阅读器
↓小说语音阅读,小说下载↓

一键清除系统垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

图片自动播放器
↓图片自动播放,产品展示↓

首页淘股吧股票涨跌实时统计涨停板选股股票入门股票书籍股票问答分时图选股跌停板选股 K线图选股成交量选股 [平安银行]

股市论谈均线选股趋势线选股筹码理论波浪理论缠论 MACD指标 KDJ指标 BOLL指标 RSI指标炒股基础知识炒股故事

商业财经科技知识汽车百科工程技术自然科学家居生活设计艺术财经视频游戏--

天天财汇 -> 科技知识 -> 所有递归都可以改写成循环吗？ -> 正文阅读

[科技知识]所有递归都可以改写成循环吗？

[收藏本文] 【下载本文】

话说递归层次比较深的话容易造成stack overflow,还被认为效率不高，而且有人表示所有的递归都可以改写成循环，这是真的吗？林锐博士的书中曾表…

可以。
尤其是尾递归，它可以固定的模式直接优化为循环；优化后的循环不再需要栈，也没了爆栈的风险，内存占用低的同时还消除了函数调用相关的一大坨开销，实属有百利而无一害。
因此，任何有一定水准的编译器都会有“尾递归优化”功能。
但其它形式的递归情况就不一样了。
除了少量可以调整到尾递归形式、但程序员能力有限写的不是尾递归的代码外，其它形式的递归虽然也可以改成循环，但它的本质仍然是递归——仅仅是把函数调用模式下默认使用的、CPU维护（所以往往更快）的栈改成了程序员自己维护的栈、然后在每次循环中手工压栈/出栈而已。
这样改写后，栈的大小由程序员控制，一定程度上可以避免爆栈问题；但问题规模过大时，该爆栈仍然会爆（比如程序员申请的栈只有5M，但程序面对的数据需要10M的栈空间才能运行）……
而且，由程序员维护的栈，除非c/c++这样语言层面允许0 overhead数据结构的语言、并且程序员正确选择了实现方案；或者语言自身提供0 overhead的栈结构，否则执行效率是一定弱于递归的——因为递归用的是CPU维护的栈。
为了避免缠杂不清，这里稍微展开一下——其实我不想扯太多无关细节的，容易造成文章内容散乱冗长……
简单说，“函数调用”本质上就是“控制局部变量的可见性”；怎么控制呢？
比如，函数A里面有两个本地变量M和N；当它递归调用自身时，我们就要把作为调用者的那个函数A（以后简称caller A）的M和N压栈、然后为被调用的那个函数A（以后简称callee A）在栈上分配新的本地变量M和N的存储空间。
其中，A的入口参数也被视为局部变量。比如这个案例：

int square(int num) {
    return num * num;
}

对应的汇编代码是：

square(int):
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        imul    eax, eax
        pop     rbp
        ret

其中第一行把外部调用者的基址寄存器保存到栈上；然后第二行把新的栈顶地址寄存器rsp的内容放进基址寄存器rbp当做新的基址；之后把传入参数num保存到rbp-4位置的内存单元（栈的增长方向之类知识我就懒得科普了，自己查）。
第四行把rbp-4位置的双字节数据载入eax，在第五行通过imul指令完成计算；第六行恢复square函数执行前的rbp内容；第七行执行ret指令（弹出栈中保存的返回地址、从而返回调用者环境继续执行）——其中的返回参数就用寄存器eax带回去，不需要额外动作。
那么，当我们要把非尾递归的函数A改写成循环时，我们就必须自己完成类似的动作——也就是要自己弄一个栈，把caller A的局部变量M、N放进去；然后为callee A分配局部变量M、N的存储空间……每一次递推循环就相当于执行了一次函数调用动作，而每一次回归循环就相当于执行了一次函数返回动作。
当callee A返回时，我们要从栈上删除给它分配的局部变量M、N，然后把caller A的局部变量M、N设置为当前变量——这就是作用域控制。
很显然，函数调用时要做的一切，在改写成循环后一个都不能少；而且会从上面那串最简洁的汇编代码变成我们自己敲的维护代码——除了高手手里的C语言，其它编程语言几乎不可能把这些维护代码编译成类似的单条机器指令（可以不是push/pop，但指令条数/访存次数你都要压缩到极致）。
这就是我前文提到的0 overhead的意思。
尤其是，如果你还傻乎乎的、每次调用都把callee的数据从堆上临时分配，那么仅此一项，执行速度慢十几倍甚至几十上百倍都有可能。
0 overhead并不会因为你用了C语言就自动得到。
更有趣的是，RISC计算机还有个“寄存器窗口”概念。
寄存器窗口的意思是，它利用CPU片上空间制作了几十上百个（甚至更多个）通用寄存器；但这些寄存器对程序来说并不是全部可见的，而是分成了若干组。
比如说，某个RISC CPU可能是这样的：
组1包含寄存器1、2、3、4、5、6，简写为ax、bx、cx、dx、ex、fx；而组2包含寄存器5、6、7、8、9、10，同样简写为ax、bx、cx、dx、ex、fx……这样的寄存器组有16组。
我们可以看到，组2的ax、bx其实就是组1的ex和fx。这是故意的。
原因很简单，这可以简化参数传递。
在caller A里面，ax、bx是它的传入参数；cx、dx用来存储局部变量M、N；当它要调用callee A时，就不需要像CISC计算机一样压栈退栈保护现场的一大堆了；而是把需要传递给callee A的两个参数放入ex和fx，之后执行call指令，于是寄存器组切换到2。接下来从头执行函数A的指令就可以了。
此时，callee A的ax、bx恰好就是caller A试图传给它的参数；cx、dx空闲，随它使用。
容易想到，callee A继续调用函数A也是同样的模式；而从callee A返回caller A时，也可以利用ax、bx带回返回值。
这个设计使得函数调用被极致优化，CPU压根不需要真的来回传递参数、清理现场，简单的切换寄存器组就行了。
当然这是简化描述；实际使用中，或许寄存器窗口大小也是可变的，毕竟两个局部变量未必够用；但寄存器太珍贵，每组大了利用不全、少了仍然要访存，那么可变大小的寄存器组就能提高寄存器利用率，但同时也会增加控制复杂度：这是一个需要根据实践数据斟酌取舍的东西。
总之，根据某款处理器支持的最大寄存器组数目，它可能支持连续10次甚至几十次函数调用都不需要访问内存，全部在寄存器里面（通过切换当前寄存器组）搞定。只有函数调用的嵌套次数超过寄存器组数目时，CPU才会真的把寄存器内容存入内存、真的执行压栈退栈内存切换等动作。
对现代处理器来说，一个访存周期就能执行70条以上的指令（奔腾三数据）；更新的CPU代价更大。
很显然的，在这种CPU上，你为了展开递归而自己实现一个栈、而不是直接递归调用、让处理器自动利用寄存器组，效率几乎一定是更差的。
除非你的编译器智能的像个妖怪、能够把你的所有这些操作都优化到寄存器里。
这就是为什么我说“由程序员维护的栈，除非c/c++这样语言层面允许0 overhead数据结构的语言、并且程序员正确选择了实现方案；或者语言自身提供0 overhead的栈结构，否则执行效率一定弱于递归”的原因。
然后，更进一步的，王垠说的递归，其实是来自函数式语言的lambda演算。
lambda演算是和图灵机等价、但并不是图灵机的另一套体系。在这个体系中，“递归”就是它的基本工作原理。
因此，流行的函数式语言，如Lisp、Haskell，它们对递归是做了极其彻底、极其有效、极其深刻的优化的。
这是因为，函数式语言自身就和数学联系紧密；很多数学概念/定理就是以递归形式定义的。比如斐波那契数列等。
函数式语言能识别这种定义，深刻理解它的语义，并针对性的给出优化。
比如，当你用递归的形式定义了一个集合、然后在后面引用它的值时，图灵系的C、Java等语言会老老实实的计算这个循环、初始化数组，然后等程序员引用它；而函数式语言却可以自动识别并执行“懒惰优化（lazy initial）”：如果你自始至终没有用这个集合，那么它就不执行相关计算；如果你引用了它的某个值，那么到你引用时它才会完成计算——尤其是，当这个递归定义不是斐波那契数列那样、必须一个个算出里面的元素的话，它甚至会自动利用通项公式一次算出对应元素的值，并不会真的从第1个元素循环计算。
而对于斐波那契数列这种情况，它也能智能的展开它、保存中间结果；比如如果你引用过斐波那契数列的第100项，那么将来引用小于100的任意项时，它都可以自动从内存提取数据，无需再次计算。
除此之外，函数式语言还能直接在编译期计算递归定义的常量、或者在程序运行时有空就计算某个计算量很大的递归数据，等等。
这些，就保证了它的递归运算不仅不会比图灵机的循环慢，反而经常有惊人的表现。
但是，这个优化仅在函数式语言中有效。
这是因为，图灵系语言中的递归往往是复杂的、随意的：程序员认为应该怎么算，就会插一行代码进去；程序员害怕哪里算错了，就会加一行日志进去……
最终，递归程序就会变得复杂、难以分析；当分析变得困难时，想要像函数式语言那样轻而易举的深度优化递归就不可能了。
事实上，哪怕今天，都仍然有不少的编译器/解释器无法支持尾递归优化！
反过来说也对：函数式语言递归优化的便利，是拿状态维护的复杂化换来的。
想像c/java/python那样，随时随地打一条日志、随时随地响应网卡中断、键盘/鼠标事件……嗯嗯，也能做。就是有点费人。

这段代码解决了我多年的问题，来源：https://jyywiki.cn/pages/OS/2022/demos/hanoi-nr.c

简而言之，就是你真的需要一个变量，来记录函数返回之后应该从去哪里。
jyy老师在B站直播操作系统课，这段代码大概出现在第一节，强烈推荐。

他们的说法放到他们各自的场景中都是正确的。
林锐是基于他所掌握的有限的语言来提出思路，是工程师思路。他主要掌握的语言是 C 语言，在 C 语言中如果使用 C 语言函数实现递归，确实效率不高，而且现实中那些难以变成循环的递归很少需要一个工程师去实现，故而，他表达的观点在他所处的应用场合中正确。
而王垠是站在科学家的角度考虑问题，把编程语言作为一门学问去看。他站得更高，看得更远，得出的结论也更具有普适性。很多语言中递归的性能并不差，而且正确实现尾递归的语言不存在栈溢出问题。
如果要打一个比方的话，可以认为林锐的观点是经典物理，而王垠的观点是相对论。相对论能够在更广泛的场合中适用，也更准确更科学。但经典物理在其特定领域的应用是很好的，并没有被相对论淘汰。

这个问题要回答完整，需要很多精力和时间。我先回答一部分。然后持续补充。
（1）递归都可以改成循环。这个命题如何评价？
我先说下结论，就是，这个命题是成立的，但是，如果只看到这个结论，对问题的认识则是片面的，不完整的。
也就是说，只看到了递归和循环的共同点：都是 EIP 在同一段代码段内反复。
而没有注意到两者在模型，重复代码段之间的层次结构，和流程控制方面的差异。
同时有很多命题加强了这种暗示，比如，遍历树，有非递归实现。比如说，我自己的技术博客上的文章：
采用栈数据结构的二叉树非递归遍历
采用路径模型实现遍历二叉树的方法
[非原创]树和图的遍历
但是，它忽略了另一个层面，就是递归和循环的思维模型上的差异性。
我先打个比喻，递归是自相似的，就好比分形图，两次重复代码段之间，是有结构，层次上的“父子”关系的。
我用鼠标手绘了一个草图，不是那么完美，感受一下就好（下图是主观感受示意，可能不太严谨的）：

而循环呢，思维模型里，它是每层循环是在一个维度上的。
递归在重复的代码片段内，每一层，都有自己独立的一套上下文。在堆叠。
循环，是在同一个层次之内的。
所以，由于这种模型上并不是完全匹配，所以虽然可以相互转换，但是实际上算法内部是有一定的“重新加工”的过程。
先举一个递归函数，改成非递归函数的例子，释放一颗二叉树，假设节点都是用 malloc，realloc 函数分配的，递归版本如下（思维是显而易见的）：

struct NODE { ...; NODE *left, *right; };
typedef struct NODE* LPNODE;

void FreeTree(LPNODE pNode)
{
    if(pNode)
    {
        FreeTree(pNode->left);
        FreeTree(pNode->right);
        free(pNode);
    }
}

改成非递归，当然有很多方式，在递归中，是最后释放根节点，在改成非递归的时候，我们可以最后释放根节点，也可以立刻就释放当前节点，只要有 stack 帮我们记着之后需要释放的节点就好办了，我们可以套用按层次（深度）遍历的非递归方法，就很容易写出：

LPNODE stack[256];
int top = -1;
void FreeTree(LPNODE pNode)
{
    LPNODE p1 = NULL;
    top = -1;
    if(pNode)
        stack[++top] = pNode;  

    while(top >= 0)
    {
        p1 = stack[top--];
        if(p1->left)  stack[++top] = p1->left;
        if(p1->right) stack[++top] = p1->right;
        free(p1);
    }
}

可以看到，这个例子中，在解决问题的思维上有微小的差异，或者说，在汇编级别上并不是对等的。在递归版本中，根节点最后被释放，而在非递归版本中，根节点第一个就被释放了。
也就是说递归和循环之间，没办法像 while 和 for 循环之间转换的那么简单且直观。为什么呢，因为两者在这种结构上有差别。
说的更细一些，就是两者指令流控制在高级语言层面不直接对等。
此外，就是递归的上下文（stack frame）会切换，循环不会切换（位于相同的 stack frame）。
循环主要是通过 continue 和 break 以及 jmp，本质上都是通过跳转来控制 eip 的。在高级语言层面上，一次循环不直接从（循环体）的中间开始。

for ( i = 0 ; i < n ;  |-> i++ --| ) //or while (...)
{                      |         |
    ... ;  <-----------+---------|   
    ... ;              |
    continue; -------->|
    ... ;              |
    break;-------|     |
    ... ;        |     |
    ... ; -------+---->|
}                |
                 |
...;   <---------|

而递归是通过 call 和 ret，也就是说，加上了 stack 的辅助来控制 eip。使得它可以从重复代码段（循环体）的中间继续运行。

void foo ( arg x )
{
    ... ;  <-----------|
    ... ;              |
    ret ; -------------+----|
    ... ;              |    |
    foo ( f(x) ); -----|    |
    ... ; <--------+--------|  //这个跳转是比较特殊的
    ... ;          |
    ... ;          |
    ret ; ---------|
}

可见，递归通过 ret 可以回到重复代码段的中间位置（由 stack 负责记忆），这个跳转，就是递归相对于循环比较特殊的地方，也导致，递归改成循环的困难点。
所以，为了把递归改成循环，在下面的例子里，我在高级语言中模拟出递归的这种流程控制。也就是通过 switch - case 语句模拟递归中 ret 的效果，让指令从被“记忆"的循环体中间位置继续运行。
这一次，举个通用的例子，来说明，递归可改写成循环这个命题为何可以成立，就是算法我是不动的，只是在高级语言层面把递归函数的痕迹给“抹掉”，是不变应万变的那种，而基本上你们在书本上等地方看到的递归改非递归，实际上都在算法上做了一些调整变化的（也就是说递归和非递归之间，是有有一定的不同）。
用斐波那契数来为例（具体什么递归函数无所谓），当然，如果我是用这样的循环，是1+1得到2，然后1+2=3, 2+3=5, 3+5=8, 5+8=13 。。。这样逐个累加得到的，那么其实算法和递归已经发生了变更。是不足以说明两者的相互转换关系的，所以我要求的是，算法不变，只是在高级语言层面，你看不到递归函数的存在而已。
在改写的时候，谨记：call 对应着在 stack 上 push 当前层次的“状态”信息，ret 对应于从 stack 上删除当前层次的“状态”信息，对应于 pop 操作。然后把汇编伪码，改成等效高级语言（这样你就看不到递归函数在高级语言层面的存在了，而算法本质上是不变的）：
因此，我先写出下面的汇编层面的伪代码：

当前层次 stack frame：

参数n  返回地址  临时变量（存储 f(n-2))
----------------------------------------
| n | retaddr | x1 | 栈增长方向 ---->
----------------------------------------
                 |
                top

n = stack[top-2]; //arg;
retaddr = stack[top - 1]; //指令流程控制
x1 = stack[top]; //f(n-2);
                 
fab(int n)
{
 1     if(n <= 1)
 2     {
 3         eax = 1; 
 4         ret;
 5     }
 6     push n-2;
 7     call fab;
 8     x1 = eax; 
 9
10     push n-1;
11     call fab;
12     eax = eax + x1;
13     ret;
}

OK，每行伪代码前面的数字，模拟的是汇编指令地址，然后我可以根据这个伪代码，改写成所谓的“循环”，实际上这个循环就是，一直循环执行指令，直到 stack 空了为止。下面是 C++ 的非递归等效代码：完全模拟上面的伪汇编的过程：

int stack[256];
int top = -1;

void push(int x)
{
	++top;
	stack[top] = x;
}

int pop()
{
	int x = stack[top];
	--top;
	return x;
}

int fab(int n)
{
	int eax = 0;
	int eip = 1;
	int retaddr;
	top = -1;

	//初始化 stack
	push(n);   //分配参数 n
	push(1);   //压入返回地址（此处的值 1 无意义）
	push(-1);  //分配临时变量 x （此处的值 -1 无意义）

	while(top >= 0)
	{
		switch(eip) //模拟指令地址
		{
		case 1:
			if(stack[top - 2] <= 1)
			{
				eax = 1;     //return 1;
				pop();       //释放临时变量 x
				eip = pop(); //弹出返回地址
				pop();       //释放参数
				break;
			}

		case 6:
			push(stack[top - 2] - 2);  //call f(n-2);
			push(8);   //压入返回地址：8；
			push(-1);  //分配临时变量 x
			eip = 1;   //call fab
			break;

		case 8:
			stack[top] = eax; //x = f(n-2);
			push(stack[top - 2] - 1); //call f(n-1);
			push(12);  //压入返回地址：12；
			push(-1);  //分配临时变量 x
			eip = 1;   //call fab
			break;

		case 12:
			eax = eax + stack[top]; //return f(n-1) + f(n-2);
			pop();        //释放临时变量 x
			eip = pop();  //弹出返回地址
			pop();        //释放参数
			break;
		}
	}

	return eax;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int x = 6;
	int y = fab(x);
	printf("fab(%d)=%d\n", x, y);
	return 0;
}

由此可见，递归都可以改成“循环”，命题成立。
我还有另一个关于递归函数的回答，里面有一个 gui 程序，模拟了递归函数的执行过程：
C语言中递归问题？ - 知乎用户的回答
（2）再说循环改递归，这个相对简单，比如说，循环比较常见的就是，让一段代码执行 N 次，我们可以写成：

for(int i = 0; i < n; i++)
{
    //...循环体
}

这里循环体可以和 i 没有任何关系。（当然，也可能发生关系）。
那么把它改成递归就很显然：

void foo(int i)
{
    if(i < n)
    {
        //... 循环体
        foo(i + 1);
    }
}

foo( 0 );

当然，循环中临时变量在循环过程中始终可见的，在循环中可以反复操作相同的数据。而递归函数切换 stack frame ，两层调用之间的临时变量都是彼此独立的，可以在递归版本中，传变量地址来操作同一个数据。
（3）递归函数效率比非递归的低。
从空间效率上，要看你怎么看这个问题，我以为是难以给什么绝对的优劣的结论，要看程序员的权衡和把握。递归会对栈有一点压力，如果在现实中把栈给撑爆了，那么是不是可以说明程序员对他的代码的运行效率太迟钝太麻木了点呢？
需了解，stack 不是用来给你存放需要占用大内存的数据的，而是存放生命周期短，占内存也不大的临时数据。
在怎么样的情况下，栈会爆掉？你可以自己估算，比如说，默认栈大小是 1MB，你在递归函数里申请 1KB 的栈上空间（例如写一个 char s[1024]; )，如果这个递归函数的最大调用深度达到 1000 以上，就导致 stack overflow。
在时间效率上呢，递归函数多了很多函数调用，当这些函数调用的数量较大时，它就会积聚成为一个时间成本，因此，这句话是成立的。（函数调用是有成本的）。
我曾经帮一个同学，给他写了一个马踏棋盘算法的非递归版本，实际上算法和递归版本是完全一致的，据他和我反馈，说非递归版本的速度要比递归函数的快。算法我是没动的，那么我想，两者的时间效率差异，就应该是由函数调用产生的开销。
好吧，我想说的还有很多，我会慢慢补充。

可以这样认为：任何计算机程序都可以表达成执行下一步和跳转……
所以，逻辑上，任何能用计算机语言表达的递归都可以写成循环。因为它会被编译成执一系列顺序指令和跳转……

[收藏本文] 【下载本文】

科技知识最新文章

《消失的问界里》为什么网传华为选择大面积

特斯拉万人大裁员涉及中国市场，销售部门是

媒体报道「特斯拉一天内失去 2 个高管和 10

去年是「大模型元年」，今年会是「AI应用落

2024 年人工智能方向的就业前景怎么样？

加:2024-03-10 13:02:17 更:2024-03-10 13:14:47

股票涨跌实时统计涨停板选股分时图选股跌停板选股 K线图选股成交量选股均线选股趋势线选股筹码理论波浪理论缠论 MACD指标 KDJ指标 BOLL指标 RSI指标炒股基础知识炒股故事

网站联系: qq:121756557 email:121756557@qq.com 天天财汇