C, Recursion, and Stack size

1. Yes, unless the function takes a variable number of arguments. Actually, even if the function takes a variable number of arguments, unless you have some funky code that decides at runtime how many vars to push onto the stack.

2. Yes, if you're on a platform where the start and end of the stack are well defined, you can examine whichever register functions as the stack pointer (if you have read access to the stack pointer that is).

Having said that, I don't think it should bother you tremendously. Just establish reasonable upper bounds on your recursive functions.

Neither the C or C++ language have the ability to determine this information. As you noted, there are OS-specific and library-specific ways to figure this out.


In practice this is not an issue.


First, why do you need recursion?

It is possible to redesign nearly any real-world algorithm into an iterative form.

One of the critical skills for all CS students is the ability to convert recursive functions into either direct calculations or iterative solutions. A good CS degree will have you spend 2-3 months on that kind of theory.

Some problems are easier to solve with recursion, but in the real world recursive solutions are rare.



Assuming recursion makes sense for the situation, you need to apply your brain.

Look at your data and look at your function. You should be able to estimate the maximum recursion depth for a given data set.

(A) Roughly how big will the function be on the stack? That is easy to estimate based on the number of local variables and embedded function calls.

(B) Roughly how deep will the recursion stack be? Recursive quicksort for data size n is roughly 2(2log2n). Recursive tree navigation will be as deep as the tree. Recursive factorial of n is n deep. If you know a little about the data size you can estimate the recursion depth.

Multiply A and B above to estimate the stack space needed. Knowing your system, will you be able to survive that?

If the answer is no, then you need to rewrite the algorithm to an iterative form.

If you aren't certain, then you should probably rewrite the algorithm, although you may be able to gracefully fail if the predicted recursive size is too large.


If the algorithm cannot easily be replaced with a non-recursive version, AND you cannot know in advance how long it will take, you should include a depth counter in your recursion to estimate how deep you have reached and when you need to abort your processing.

The simplest solution for removing recursion is to simply maintain your own stack, instead of using the function call stack. Then you can make your stack grow as big as you like.

Thanks everyone for your replies so far.

Quote:

Original post by Codeka The simplest solution for removing recursion is to simply maintain your own stack, instead of using the function call stack. Then you can make your stack grow as big as you like.

I agree; that's the easy answer, and I recognize when it's useful. Though there's part of me that's bothered by the idea of maintaining your own stack when you've got a stack pointer register built right into your silicon.

To get across what's really irking me though, consider this argument by reductio ad absurdum: If you don't know how many function calls deep you can go (or how deep you are), then in principle you can't safely call any function! I know I'm taking the argument here to logical extremes and in practice you've got plenty of headroom, but in principle it seems very dangerous whenever you,
1. have limits,
2. don't know when you've reached them,
and
3. will quietly create security vulnerabilities whenever you do.

For another beast with the same features 1-3, consider C-style null-terminated strings with unspecified buffer sizes, and the security problems they create.

So... There are no commonly used (but perhaps OS-specific) libraries or compiler intrinsics that people use to deal with this?

Quote:

Original post by Emergent 3. will quietly create security vulnerabilities whenever you do.

I'm not aware of any security vulnerabilities associated with stack overflows (note: stack overflows, not stack-based buffer overflows), unless you count process termination (a form of denial of service, I guess) as a security vulnerability (but I wouldn't).

Quote:

Original post by Codeka unless you count process termination (a form of denial of service, I guess) as a security vulnerability (but I wouldn't).

I would. Unintended termination is a great vulnerability. Think of the poor plane pilot, who solely relies on fly-by-wire, and then the system terminates; maybe a termination during a meltdown, or during car-brake-assist short before a crash.

I would say, unintended behaviour is always a vulnerability.

There was quite a discussion about this in regards to Joint Strike Fighter AV Rule 119: Functions shall not call themselves, either directly or indirectly (i.e. recursion shall not be allowed) a while back you might be interested in.
But yeah, bottom line is to avoid recursion in "critical" i.e. code you want to be sure works;)

[Edited by - daviangel on July 29, 2009 7:39:36 PM]

Quote:

Original post by daviangel There was quite a discussion about this in regards to Joint Strike Fighter AV Rule 119: Functions shall not call themselves, either directly or indirectly (i.e. recursion shall not be allowed) a while back you might be interested in. But yeah bottom avoid recursion in "critical" i.e. code you want to be sure works;)

Das trifft zu wie die Faust aufs Auge, we say in germany :D (that approximately translates to: "It hits/fits [the point of interest] like the fist hits the eye")

Nice link, I always love industry programming talk (e.g. MISRA papers, or, for Linux, there are Appolo space craft emulators, and things like that).

The problem with stack is in how to proceed. This in part has to do with the way language is designed.

char foo() {  char x[ARBITRARY_LARGE_VALUE];  return x[ARBITRARY_LARGE_VALUE-1]}int main() {  char z = foo();  std::cout << z;  return 0;};

What do you do? Or better yet, assuming you are able to handle stack failure, how do you determine where to continue? Unlike exception handlers, compiler cannot simply choose to skip the cout line, since it depends on z, and resume. I don't believe that handling this by putting every single function call into try/catch block would be of much help. Regardless of how one would handle it, the code above would never be able to run.

And since stack overflow can occur at any given time (being a linker property, and considering it can be changed later), code itself would need to check it on every function call. Depending on OS, entire stack is typically not committed at start, meaning that it's theoretically possible that expanding the stack fails due to running out of physical memory (either physical or virtual).

IIRC, MSVC's runtime does insert stack checks into code under certain settings, but I never looked into detail what exactly it's checking. I believe gcc also offers options to check for stack corruption.


Fortunately, in practice applications fall into two categories:
- Those for which stack is a non-issue
- Those which blow up fast (large allocations, infinite recursion)

Quote:

Original post by Antheus The problem with stack is in how to proceed. This in part has to do with the way language is designed. char foo() { char x[ARBITRARY_LARGE_VALUE]; return x[ARBITRARY_LARGE_VALUE-1]}int main() { char z = foo(); std::cout << z; return 0;}; What do you do? Or better yet, assuming you are able to handle stack failure, how do you determine where to continue? Unlike exception handlers, compiler cannot simply choose to skip the cout line, since it depends on z, and resume.

If foo() would throw a stack_overflow (or even an out_of_memory -) exception, why should the rest of main() not be skipped? (maybe I miss something). Imho, above code should be possible as that is possible:

int main() {  char *z = new char; // could throw  std::cout << *z;  delete z;  return 0;};

The "cout line" in this example also depends on the value of *z, but if the heap is full, it won't be executed either.

Quote:

Fortunately, in practice applications fall into two categories: - Those for which stack is a non-issue - Those which blow up fast (large allocations, infinite recursion)

I recently experienced the "hidden" category (maybe because it was on Linux):

- Those which blow up slowly:

void f() { f(); }

Something with a tad more data just recently pushed me into a debugging session, where I started my application, went away for like 2 minutes or so, and it was still running (that is, it was on a Linux box). If I think about it, my box has 2GiB of physical RAM, plus several GiBs of swap. Let's assume my function had an overhead of 8byte. Just the physical RAM would allow for 2GiB / 8Byte = 268,435,456, then, my application has an address space of 4 GiB, this would mean I could have a recursion depth of 400M. Add in some swapping time or other tasks, and whoopsa, my app would run minutes before crash.

Quote:

Original post by phresnel The "cout line" in this example also depends on the value of *z, but if the heap is full, it won't be executed either.

But you can catch bad_alloc and handle it.

Quote:

why should the rest of main() not be skipped? (maybe I miss something)

Yes, but this is what happens right now. If you blow the stack, application dumps or crashes - since there is no way to tell where to go to resume or how.


There are vendor-specific ways of handling stack failures, but in some cases they simply aren't possible.

This is why stack should generally be used for static and compile-time known sizes. For recursive algorithms maximum depth can usually be determined in advance. For other purposes, pre-allocating on heap works up to addressable space, and using that is a better option with effectively no performance penalty. Instead of using call stack, on uses custom allocated block of memory of arbitrary size.

But again, the class of algorithms in practice is small enough for this not to be an issue.

Quote:

this would mean I could have a recursion depth of 400M

This would be a nice example of why it doesn't matter much. Such recursion depth is effectively never needed. Even worst-case QSort with n^2 depth is already, or trivially, implemented to only have depth of logn - or about 64 on 64-bit address space.

Quote:

Original post by Antheus Quote: Original post by phresnel The "cout line" in this example also depends on the value of *z, but if the heap is full, it won't be executed either. But you can catch bad_alloc and handle it. Quote: why should the rest of main() not be skipped? (maybe I miss something) Yes, but this is what happens right now. If you blow the stack, application dumps or crashes - since there is no way to tell where to go to resume or how.

It would resume in the catch block that encloses the point of failure at most, like with all exceptions. I agree that there could be unsolvable problems on some hardware, but I don't see a problem with the program logic itself, if implementible. If I catch an exception, I can anyways make no assumption *where* the try-block throwed off (except by using some handcoded state variables or other hacks like that).

Quote:

There are vendor-specific ways of handling stack failures, but in some cases they simply aren't possible.

Okay.

Quote:

This is why stack should generally be used for static and compile-time known sizes. For recursive algorithms maximum depth can usually be determined in advance. For other purposes, pre-allocating on heap works up to addressable space, and using that is a better option with effectively no performance penalty. Instead of using call stack, on uses custom allocated block of memory of arbitrary size.

Agree.

Quote:

Quote: this would mean I could have a recursion depth of 400M This would be a nice example of why it doesn't matter much. Such recursion depth is effectively never needed. Even worst-case QSort with n^2 depth is already, or trivially, implemented to only have depth of logn - or about 64 on 64-bit address space.

On Windows under MSVC6, when I was a young programmer (:S), I received stack overflows much sooner, for some functions that was at a depth of 200 (two-hundred). But yes, such depth is generally not reached in an imperative language. But there are also loop constructs baseed on recursion that are hard to convert to ordinary loops (non tail recursive functions) in a functional programming language that is state free and therefore has no loop. But yes, that is rare.

Still, such 400M recursion depth would be the death of a fighter pilot in steep flight.

Quote:

daviangel wrote: There was quite a discussion about this in regards to Joint Strike Fighter AV Rule 119: Functions shall not call themselves, either directly or indirectly (i.e. recursion shall not be allowed) a while back you might be interested in. But yeah bottom avoid recursion in "critical" i.e. code you want to be sure works;)

Thanks for the article; I'll take a look at it. :-)

A thought: If the rule referenced above is followed, then it would seem that, in principle, it should be possible to perform static maximum-stack-depth analysis automatically at link-time. To generalize this thought, such a tool could also detect functions-calling-themselves and raise warnings. In graph-theoretic terms, you'd generate a directed graph where nodes are function names and edges are calls, and require that it have no cycles. Again in principle, the programmer could then choose to deal with these warnings himself at runtime using appropriate libraries.

Speaking of which... I've found some platform-specific ways to catch stack overflow at runtime:

1. For the Windows + Visual Studio + x86 case, the article How to trap stack overflow in a Visual C++ application describes pretty much exactly what I'd had in mind.

2. On Linux (and other platforms?), the libsigsegv library can be used to catch the signal generated by stack overflow and implement error handlers.

[Edited by - Emergent on April 2, 2009 2:05:02 PM]