C ++是否限制递归深度?

问题描述 投票:56回答:6

在Python中,最大递归深度。似乎是因为Python是解释而不是编译的。 C ++是否具有相同的概念?还是仅与RAM限制连接?

c++ recursion limit
6个回答
48
投票

C ++中的限制是由于堆栈的最大大小。通常,它比RAM的大小小几个数量级,但仍然很大。 (幸运的是,字符串contents之类的大对象通常不保存在堆栈本身上。)

堆栈限制通常可以在操作系统级别进行调整。 (如果您在Unix上,请参阅内置ulimit shell的文档。)此计算机(OSX)上的默认值为8 MB。

[编辑]当然,在计算可递归的深度时,堆栈的大小本身并不能完全有效。要知道这一点,您必须计算递归函数(也称为堆栈框架)的激活记录(或记录)的大小。 (我知道)最简单的方法是使用反汇编程序(大多数调试器的功能),并在每个函数的开头和结尾读取堆栈指针调整的大小。太乱了(您可以采用其他方法来计算-例如,计算两次调用中变量的指针之间的差异-但它们甚至还比较麻烦,尤其是对于可移植代码而言。从反汇编中读取值更容易IMO。)]


22
投票

否,C ++没有明确的递归深度。如果超过了最大堆栈大小(在Windows上默认为1 MB),则C ++程序将溢出堆栈并终止执行。


6
投票

C或C ++标准中没有递归深度跟踪或限制。在运行时,深度受堆栈可以增长到多大的限制。


3
投票

C ++确实具有最大递归深度,受堆栈限制。但是,现代操作系统能够在用户空间堆栈填满时动态扩展它,从而仅通过内存空间和内存碎片来限制递归深度。


3
投票

我相信限制是平台上可用堆栈的大小。据我了解,在Linux上默认为8K 8MB,但是现代内核可以动态调整堆栈大小。


3
投票

Python在递归调用上具有tunable limit,而C ++受堆栈大小限制。

此外,许多语言或编译器都可以通过删除调用方的堆栈框架来优化尾递归,这样就不会占用额外的堆栈空间。 (在尾部递归中,调用函数执行的唯一操作是在进行递归调用后返回递归调用的返回值。)

int fact(int n, int accum=1){
  if (n==0) return accum;
  else return fact(n-1,n*accum); //tail recursion here.
}

Python不会优化尾部递归(但是stackless Python会这样做,并且C ++不需要尾部递归优化,但是我相信gcc会优化尾部递归。 JVM没有优化尾部递归,尽管Scala语言在某些常见的书面案例中做了优化。 Scheme和Lisp(可能还有其他功能语言)要求优化尾递归。

© www.soinside.com 2019 - 2024. All rights reserved.