0x00

前段时间群里的dalao提出了这个问题:

一个C程序最多能递归多少次?

A.无数次
B.2^32次/2^64次(由操作系统位数决定)
C.无法确定
What's ur answer¿
dalao给出的C语言例程:

#include <stdio.h>
void Main(unsigned long long t);
int main()
{
Main(0);
}
void Main(unsigned long long t)
{printf("第%llu次递归\n",t);Main(++t);
}

我写的C++例程:

#include <iostream>
using namespace std;
long long int i;
void recursion(){
i++;
cout << "Recursion count:" << i << endl;
recursion();
}
int main(){
recursion();
return 0;
}

不管运行哪个程序,它都会以错误码-1073741819(0xC0000005)结束运行(IDE为CodeBlocks,Win7旗舰版,内存1.5GB,虚拟化技术QEMU/KVM),它的状态码一般是内存溢出造成的,但dalao文章里给的是堆栈溢出的状态码。
这可能是程序循环输出数据,占用了大量无用内存,C0000005的状态码(内存访问冲突)也证实了这个猜想。

cout << "Recursion count:" << i << endl;

这行代码删去,即可得到另一个不同的状态码:-1073741571(0xC00000FD),即栈溢出。
写程序时,递归返回逻辑出现问题等原因导致递归过于深入便会导致程序出现异常。

0x01

过度递归怎么会引发栈溢出呢?
将代码改动一下(此前使用CodeBlocks作为IDE,它使用GNU编译器,无论是_asm还是_mBeginASM都无法内联汇编代码,这段代码使用VC++ 6.0编译器):

#include <iostream>
using namespace std;
__int64 i; //long long int的写法并不允许出现在VC++中,但它提供了__int64这种数据类型,可达到与long long int一样的效果
void recursion(){
i++;
if(i>=5000){
    __asm int 3//使用asm block在递归次数超过5000时发起int 3中断,方便调试
}
recursion();
}
int main(){
recursion();
return 0;
}

生成程序后,用OllyDbg加载程序并运行,程序会暂停(触发int 3)
这时看一下调用树

call-tree-recursion
call-tree-recursion

程序的调用树已经很长了
众所周知,一个程序在调用一个函数时,便会在堆栈里存入一些数据,用于标记返回地址等信息
若递归使用不当,便会导致大量数据存入堆栈
而堆栈一般只有2-3M的空间,数据过多后便会溢出,就造成了栈溢出

0x02

说了这么多堆栈、栈溢出之类的东西,它们到底是什么呢?
首先我们要知道堆栈是什么东西
其实它是两个东西,分为堆和栈
堆你可以看成一个二叉树

heap
heap

图片来源:https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin

它每个节点的值都不大于/不小于其父节点的值,且它永远是个完全二叉树
栈则是一种先进后出的东西

stack
stack

就像一个桶,比如我要把c拿出来,就得先把a、b拿出来才能把c拿出来,拿完之后可能还得把a、b放回去
因此栈的操作方式只有两种:入栈(push)和出栈(pop)
入栈就是把一个数据放到栈顶,出栈就是把栈顶的数据拿出来
那么堆和栈又有什么区别?
栈空间是由操作系统分配的,用于存储函数传参以及局部变量等内容,且使用一级缓存,调用完成后便会立即释放
而堆空间则是程序申请的,若不被释放则会一直保留,可能会在程序结束时被操作系统回收,且堆使用二级缓存,生命周期由虚拟机的垃圾回收算法决定。
那么栈会溢出,堆会溢出吗?
会,不在我知识范围内
其原理可参考https://blog.csdn.net/nocbtm/article/details/88428596

0x03

(1)参考文献
1.c语言函数最大能递归的次数多少-博客园OBJECT-A
2.堆和栈的区别是什么-php中文网
3.堆(数据结构)-百度百科

第一次用Markdown写文章耶...排版可能不大好
见 谅 辣