Does C++ limit recursion depth?

Question

In Python there is a maximum recursion depth. Seems it is because Python is an interpreter, not a compiler. Does C++ have the same concept? Or it only connected with RAM limit?

Answer 1

C++ does have a maximum recursion depth, limited by the stack. However, modern operating systems are able to expand a userspace stack dynamically as it fills up, limiting recursion depth by memory space and memory fragmentation only.

Answer 2

I believe the limit is the size of the stack available on the platform. From what I've read, it's 8K 8MB by default on Linux, but modern kernels can adjust the stack size dynamically.

Answer 3

The limit in C++ is due to the maximum size of the stack. That's typically less than the size of RAM by quite a few orders of magnitude, but is still pretty large. (Luckily, large things like string contents are typically held not on the stack itself.)

The stack limit is typically tunable at the OS level. (See the docs for the ulimit shell built-in if you're on Unix.) The default on this machine (OSX) is 8 MB.

[EDIT] Of course, the size of the stack doesn't entirely help by itself when it comes to working out how deep you can recurse. To know that, you have to compute the size of the activation record (or records) of the recursive function (also called a stack frame). The easiest way to do that (that I know of) is to use a disassembler (a feature of most debuggers) and to read out the size of the stack pointer adjustments at the start and end of every function. Which is messy. (You can work it out other ways – for example, computing the difference between pointers to variables in two calls – but they're even nastier, especially for portable code. Reading the values out of the disassembly is easier IMO.)

Answer 4

There's no recursion depth tracking or limit in the C or C++ standards. At runtime, the depth is limited by how big the stack can grow.

Answer 5

No, C++ does not have an explicit recursion depth. If the maximum stack size is exceeded (which is 1 MB by default on Windows), your C++ program will overflow your stack and execution will be terminated.

Answer 6

Python has a tunable limit on recursive calls, while C++ is limited by the stack size.

Additionally, many languages or compilers can optimize tail recursion by removing the caller's stack frame so that no additional stack space is consumed. (In tail recursion, the only thing the calling function does is after making the recursive call is to return the recursive call's return value.)

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

Python does not optimize tail recursion (but stackless Python does), and C++ does not require tail recursion optimization, but I believe that gcc optimizes tail recursion. The JVM does not optimize tail recursion, though the Scala language does in certain common documented cases. Scheme and Lisp (and probably other functional languages as well) require that tail recursion be optimized.