72

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?

Improve this question
4
  • 2
    I assume you mean a maximum recursion depth. (how deep recursion is allowed to be before you encounter an error) Commented Apr 13, 2010 at 14:01
  • 1
    I'm not seeing why being an interpreter/compiler would have anything to do with this. For example, Stackless Python is still an interpreter, but doesn't use the C stack for its stack frames and therefore doesn't have the same issue, no? Commented Apr 13, 2010 at 14:10
  • note there are C++ and Python implementations that can do tail call eliminations to avoid hitting stack limits in those cases. Commented Apr 13, 2010 at 14:11
  • @Ken stackless will still exhaust resources eventually if the recursive call can't be eliminated e.g. tail call optimization Commented Apr 13, 2010 at 14:14

6 Answers 6

Reset to default
64

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

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

I know I should have said MiB for the units, but that means something else entirely to me. So I'll go for 67.1 megabits instead!
On Windows machines, you can A. handle stack overflow conditions safely, and B. set the stack depth individually per executable (it's a linker option). Unix machines typically use much deeper stacks (8MB) than Windows (1MB) by default due to these features. +1
I think that there are differences in how the two OS families handle virtual memory in this area too. The details start to get rather non-trivial.
Just an FYI for readers: You may have seen "activation record" called "stack frame" in some circles :)
here on linux (x86_64), help ulimit says that the stack size can be retrieved by running ulimit -s which yields 8192, relative to unlimited yielded by running it without the -s switch. The default limit used if none is provided is -f: the maximum size of files written by the shell and its children. YMMV on other Unixes [Unices?], but I thought it was worth pointing out.
|
33

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.

Improve this answer

2 Comments

Yep. +1. Additionally, it's important to note that the termination is instant -- similar to calling TerminateProcess. None of your process' nice shutdown features (i.e. DLL_PROCESS_DETACH, DLL_THREAD_DETACH, etc) will be called.
Absolutely - this is one of the nastier ways a program can be terminated.
6

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.

Improve this answer

2 Comments

Actually, the limitation is a combination of the addressing capability of the platform, the amount of memory available to the process and any limitations set by the compiler. In general, applications can override the stack and perform undefined behavior.
Also, any ulimit-style runtime limitations, or in the case of threads, any limits set during thread creation. I'm not sure if, by "override the stack", you mean "set it to a size the OS cannot support (e.g. unlimited) because some other limit will be reached first", or "push way too much on the stack and overrun the end." Nothing like having 256K of automatic storage in your recursive function, overshooting an insufficient number of "read only" stack protection pages at the end, and getting a segmentation fault or heap corruption instead of a write-to-read-only-page error...
4

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.

Improve this answer

Comments

3

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.

Improve this answer

5 Comments

Hmm.. I'm not entirely positive Unixen provide that feature. But I could be very very wrong :) It seems boost::regex would use such features if they were available... it makes use of them on Windows.
Dynamic stack expansion sounds interesting. Do you have a reference?
setrlimit(2) describes a RLIMIT_STACK resource, and the man page makes no mention of it being Linux-specific. linux.die.net/man/2/setrlimit
Ah -- I see why boost::regex doesn't do it then. You need to setup a SIGSEGV handler and catch all such exceptions on an alternate stack to handle it. And hope there's no legitimate access violation lying around somewhere.
the only thing I have read in the past about stack extension was about paging. basically pages (4Kb) are not allocated for the stack, but gets allocated dynamically when the stack pointer wants to access the guard page. (the guard page is the page right after the last allocated page). But it does NOT free one from the max limit of 1MB. the limit is not your RAM size.
3

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.