递归算法具有程序容易编写的特点;然而,由于编译器预分配堆栈空间的限制,递归深度并不是无限制的。
在递归过程中,系统将对当前程序运行状态保存(压入堆栈),并将参数压栈,然后递归。
在递归完成后,则做出栈操作。
当递归深度很深时,由于堆栈满,递归无法继续。
那么,递归深度到底是多少呢?如果我们创建无参数传递的递归,是否会更节省内存,从而,加大递归深度呢?
程序:测试C++编译器的递归深度
/* 测试C++语言的递归深度 G++结果: F: 43273 F1: 43273 F2: 43266 VC2012结果: F:85588 F1:44998 F2: 42773 */ #include <iostream> using namespace std; int n; int times = 0; void F() { if (n == 1) return; else { cout << times++ << endl; n = n - 1; F(); } } void F1(int n) { if (n == 1) return; else { cout << times++ << endl; n = n - 1; F1(n); } } typedef struct data { int a, b; } Data; void F2(int n, Data data) { if (n == 1) return; else { cout << times++ << endl; n = n - 1; F2(n, data); } } int main() { n = 1e6; //F(); //F1(n); Data data; F2(n, data); cout << "end"; return 0; }
从上述程序似乎可以看出,在确定的编译器及编译参数下,不同参数传递方式似乎对递归深度没有太大影响。
问题:到底是编译器对递归深度有限制?还是内存不够用了?
结果:递归算法应慎用!
原文链接: https://www.cnblogs.com/javawebsoa/archive/2013/04/18/3028876.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/85130
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!