Recursion unsafe in C/C++?

The question of "why disallow recursion in C++?" came up in a comment to the C++ coding standards for the Joint Strike Fighter. I'm reposting a version of the comment I left there, because I wish someone had explained this to me a long time ago.

Recursion isn't safe in C/C++ because there is no reasonable way to deal with running out of call stack space. Even if you dynamically allocate stack frames from the heap, you still can run out of heap and how do you handle the error then?

You might convert the failed call stack allocation into an exception that unwinds the stack until an out-of-stack exception handler is found, but the problem is that any function in any library called from a recursive routine might be the call that blows the stack.

To use exception handling you must now implement catch-like error handling to deal with any failed function calls, and the error handling cannot require any additional stack. And while unwinding the exception, stack allocated object destructors also may not use any additional stack space. So long RAII. Exception handling isn't a workable solution for stack failures.

So for code that needs to be proven it cannot blow the stack, the simple solution is to disallow recursion altogether. With recursion disallowed, it it becomes a tractable problem to statically analyze the code and determine the absolute maximum amount of stack space necessary. Preallocate that amount of stack and you don't need to worry about error handling for stack failures, they aren't possible.

Fortunately any algorithm that can be written recursively can be rewritten iteratively by keeping a heap-based stack object (and if it can be written completely tail-recursively, you don't even need a stack). The code might be uglier when written iteratively, but it's always possible and you can do error handling for failed stack allocations.

Posted February 18, 2008 7:28 PM