What's the maximum depth of recursion?

Question

i wonder what's the maximum depth of a recursion function. I know it has relationship with the stack size. But what's the relationship? If i write a function in 32-bit machine which dose nothing but call itself, What's the maximum depth?

unsigned long times=0;
void fun()
{
     ++times;
     fun();
}

Then what's value of 'times' when the stack overflow?

man, that depends on a heckuva lot things. there's just too much of them for anyone to sensibly give an absolute, always-correct "the maximum depth is XY" answer. — The Paramagnetic Croissant, Jan 12 '15 at 11:02
The maximum depth of recursion does not only depend on the stack size, but also on the total encoding size of the arguments for each recursive call. Just roughly guessing, for your example, at least the return address (which will probably be encoded in 4 bytes) must be stored, so the maximum depth will be roughly the stack size divided by four, depending on how large the call stack is at the beginning of the recursion. — Codor, Jan 12 '15 at 11:02
In cases where the compiler can perform tail recursion optimizations, there is no maximum depth. — Panagiotis Kanavos, Jan 12 '15 at 11:05
If you need an approximate value, it's hundreds of thousand of calls on modern PC's. But as @Codor said, the real value strongly depends on arguments and local variables. — Mark Shevchenko, Jan 12 '15 at 11:08
Thank you. I just use a example to understand the relationship, in fact i don't ask the exact value of 'times'. I know it's very complex. — Roger.Kang, Jan 12 '15 at 11:09
I don't understand what is "unclear" about this question, but for what it's worth, it's a duplicate of [this one](http://stackoverflow.com/questions/10145994/what-is-the-order-of-magnitude-of-the-maximum-number-of-recursive-calls-in-c), and a few similar ones. — jogojapan, Jan 12 '15 at 11:39

samgak · Answer 1 · 2015-01-12T11:38:44.037

The relationship is roughly this:

Maximum recursion depth = ((Stack size) - (Total size of stack frames in call chain up to the recursive function)) / (Stack frame size of recursive function)

The stack frame is the data that gets pushed onto the stack each time you make a function call. It consists of the function return address, space for parameters (that weren't passed in registers) and space for the local variables. It will differ for different functions but it will be constant for a given function recursively calling itself at each call.

It follows from this that a recursive function with a large number of parameters and/or large number of local variables will have a larger stack frame size, and therefore a smaller maximum recursion depth for a stack of a given size.

If the compiler performs tail recursion optimization, then the stack frame size is effectively zero after the top-level call, so the formula gives a divide by zero: no max recursion depth.

Everything I've said here probably has multiple exceptions to the rule, but this is the basic relationship.

What's the maximum depth of recursion?

1 Answers1