Does C++ limit recursion depth?

C++RecursionLimit

C++ Problem Overview


In Python there is a maximum recursion depth. Seems it is because Python is interpreted rather than compiled. Does C++ have the same concept? Or it is connected only with RAM limit?

C++ Solutions


Solution 1 - C++

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.)

Solution 2 - C++

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.

Solution 3 - C++

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.

Solution 4 - C++

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.

Solution 5 - C++

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.

Solution 6 - C++

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.

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionNarekView Question on Stackoverflow
Solution 1 - C++Donal FellowsView Answer on Stackoverflow
Solution 2 - C++Justin EthierView Answer on Stackoverflow
Solution 3 - C++Mike DeSimoneView Answer on Stackoverflow
Solution 4 - C++Ken BloomView Answer on Stackoverflow
Solution 5 - C++Ignacio Vazquez-AbramsView Answer on Stackoverflow
Solution 6 - C++Andy ShellamView Answer on Stackoverflow