70

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?

SU3
  • 5,064
  • 3
  • 35
  • 66
Narek
  • 38,779
  • 79
  • 233
  • 389
  • 2
    I assume you mean a *maximum* recursion depth. (how deep recursion is allowed to be before you encounter an error) – jalf Apr 13 '10 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? – Ken Apr 13 '10 at 14:10
  • note there are C++ and Python implementations that can do tail call eliminations to avoid hitting stack limits in those cases. – jk. Apr 13 '10 at 14:11
  • @Ken stackless will still exhaust resources eventually if the recursive call can't be eliminated e.g. tail call optimization – jk. Apr 13 '10 at 14:14

6 Answers6

61

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

Donal Fellows
  • 133,037
  • 18
  • 149
  • 215
  • 2
    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! – Donal Fellows Apr 13 '10 at 14:07
  • 2
    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 – Billy ONeal Apr 13 '10 at 14:08
  • 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. – Donal Fellows Apr 13 '10 at 14:14
  • 4
    Just an FYI for readers: You may have seen "activation record" called "stack frame" in some circles :) – Billy ONeal Apr 13 '10 at 14:15
  • Here on my Mac (Snow Leopard) ulimit tells me the stack limit is unlimited :o – Björn Apr 13 '10 at 14:17
  • It's policy. Don't fret about it. – Donal Fellows Apr 13 '10 at 14:34
  • 1
    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. – Chris Browne Jun 01 '12 at 13:44
  • is there any method to detect when an application recurses over the stack size? Would it be possible to create an exeption? – waynix Jun 25 '12 at 08:21
  • @waynix: Awkward, really. You get a signal at some point after exceeding the stack size (and you need to have installed a signal handler suitably, with its _own_ stack because you're out of room in the main one) but recovering is very difficult as you don't know what state the system is in at that point (the problem being how to release resources). It gets even harder with multithreaded code, as the threads other than the main one have their own stack size limits that are set at thread creation time. It's all really horrible and you should write your code to avoid storing lots on the stack… – Donal Fellows Jan 28 '13 at 14:18
  • @DonalFellows unless you are hard real time or embedded and need to worry about heap allocations – Tim Seguine Sep 09 '13 at 16:19
  • string content is on the stack if not constant like in this `char s[] = "stuff";` – v.oddou Mar 14 '15 at 03:21
32

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.

Justin Ethier
  • 131,333
  • 52
  • 229
  • 284
  • 4
    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. – Billy ONeal Apr 13 '10 at 14:12
  • 4
    Absolutely - this is one of the nastier ways a program can be terminated. – Justin Ethier Apr 13 '10 at 14:17
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.

Mike DeSimone
  • 41,631
  • 10
  • 72
  • 96
  • 1
    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. – Thomas Matthews Apr 13 '10 at 16:53
  • 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... – Mike DeSimone Apr 14 '10 at 03:33
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.

Ken Bloom
  • 57,498
  • 14
  • 111
  • 168
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.

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
  • 1
    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. – Billy ONeal Apr 13 '10 at 14:17
  • Dynamic stack expansion sounds interesting. Do you have a reference? – Don Wakefield Apr 13 '10 at 14:17
  • `setrlimit(2)` describes a `RLIMIT_STACK` resource, and the man page makes no mention of it being Linux-specific. http://linux.die.net/man/2/setrlimit – Ignacio Vazquez-Abrams Apr 13 '10 at 14:25
  • 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. – Billy ONeal Apr 13 '10 at 14:32
  • 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. – v.oddou Mar 14 '15 at 03:24
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.

Andy Shellam
  • 15,403
  • 1
  • 27
  • 41