What is the order of magnitude of the maximum numb

问题:

I have a recursive function which calls itself a very large number of times given certain inputs - which is exactly what it should do. I know my function isn't infinitely looping - it just gets to a certain number of calls and overflows. I want to know if this is a problem with putting too much memory on the stack, or just a normal restriction in number of calls. Obviously it's very hard to say a specific number of calls which is the maximum, but can anybody give me a rough estimate of the order of magnitude? Is it in the thousands? Hundreds? Millions?

回答1:

It completely depends on how much information you use on the stack. However, the default stack on Windows is 1MB and the default stack on Unix is 8MB. Simply making a call can involve pushing a few 32bit registers and a return address, say, so you could be looking at maybe 20bytes a call, which would put the maximum at about 50k on Windows and 400k on Unix- for an empty function.

Of course, as far as I'm aware, you can change the stack size.

回答2:

So, as you've guessed, the problem is the (eponymous) stack overflow. Each call requires setting up a new stack frame, pushing new information onto the stack; stack size is fixed, and eventually runs out.

What sets the stack size? That's a property of the compiler -- that is, it's fixed for a binary executable. In Microsoft's compiler (used in VS2010) it defaults to 1 megabyte, and you can override it with "/F " in compiler options (see here for an '03 example, but the syntax is the same).

It's very difficult to figure out how many calls that equates to in practice. A function's stack size is determined by it's local variables, the size of the return address, and how parameters are passed (some may go on the stack), and much of that depends on architecture, also. Generally you may assume that the latter two are less than a hundred bytes (that's a gross estimate). The former depends on what you're doing in the function. If you assume the function takes, say, 256 bytes on the stack, then with a 1M stack you'd get 4096 function calls before overflowing -- but that doesn't take into account the overhead of the main function, etc.

You could try to reduce local variables and parameter overhead, but the real solution is Tail Call Optimization, in which the compiler releases the calling function as it invokes the recursing function. You can read more about doing that in MSVC here. If you can't do tail calls, and you can't reduce your stack size acceptably, then you can look at increasing stack size with the "/F" parameter, or (the preferred solution) look at a redesign.

回答3:

One option for you may be to change/increase the default stacksize. Here's one way http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.80).aspx

回答4:

There are tools to measure the stack usage. They fill the stack in advance with a certain byte pattern and look afterwards up to what address it got changed. With those you can find out how close to the limit you get.

Maybe one of the valgrind tools can do that.

回答5:

The amount of stack space used by a recursive function depends on the depth of the recursion and the amount of memory space used by each call.

The depth of the recursion refers to the number of levels of call active at any given moment. For example, a binary tree might have, say, a million nodes, but if it's well balanced you can traverse it with no more that 20 simultaneous active calls. If it's not well balanced, the maximum depth might be much greater.

The amount of memory used by each call depends on the total size of the variables declared in your recursive function.

There's no fixed limit on the maximum depth of recursion; you'll get a stack overflow if your total usage exceeds the stack limit imposed by the system.

You might be able to reduce memory usage by somehow reducing the depth of your recursion, perhaps by restructuring whatever it is you're traversing (you didn't tell us much about that), or by reducing the total size of any local objects declared inside your recursive function (note that heap-allocated objects don't contribute to stack size), or some combination of the two.

And as others have said, you might be able to increase your allowed stack size, but that will probably be of only limited use -- and it's an extra thing you'll have to do before running your program. It could also consume resources and interfere with other processes on the system (limits are imposed for a reason).

Changing the algorithm to avoid recursion might be a possibility, but again, we don't have enough information to say much about that.