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
Comments
Linear code is also faster than recursive code, since the stack is very slow. This can be especially noticed in the QuickSort algorithm, which was originally recursive, but I've written a linear optimized version of it.
Mika Heinonen, February 19, 2008 12:43 AM
It seems like a bit of a strange restriction to me. Perhaps you can always accomplish what you need without recursion, but sometimes converting an algorithm from recursive to iterative is complex, and will introduce errors. Why not just require proof that the recursion won't overflow the stack? For example, you could require that every recursive function have an explicit depth parameter and disallow recurring more than 30 calls deep. This is a convention that is easy to follow and easy to verify.
Even with an iterative algorithm, how do you prove that the loop will terminate?
And once you start down this path of prohibiting complex structures, where do you stop? Why not prohibit pointers because it can be difficult to guarantee they are not NULL?
Ned Batchelder, February 19, 2008 8:38 AM
There are ways to validate recursion won't blow the stack, but it's not something that can be easily automated for static checking, it's going to require human intervention. But by simply disallowing recursion, you can easily compute the maximum possible stack depth statically (though function pointers can make things difficult).
I'm not against using recursion in C/C++, but in avionics it's probably a good idea to ban it. Eliminating it means you will never have to worry about blowing the stack, the failure scenario simply doesn't exist in the code.
But that's a problem in any Turing-equivalent language. Iterative vs. recursive doesn't make a difference.
Because C++ code can do error checking to deal with failed allocations, etc. The same cannot be said for a out-of-callstack conditions, where any function call could be the one that fails, including the error handling functions.
Damien Katz, February 19, 2008 9:14 AM
All nice and good for avionics, but can we force the auto manufacturers to go this way as well?
Ever time I see one of those ads for Ford "powered by Microsoft" it scares the hell out of me.
Craig Wiseman, February 21, 2008 3:56 PM
>The code might be uglier when written iteratively,
Then why not program in Assembly only..
I think recursion is so much close to way human brain thinks that it would be self defeating to not have a recursion available in high level language like c/c++. Usecases may vary. You may opt not to use some features of language. Eliminating them altogether sounds unreasonable though.
AD, March 6, 2008 4:26 PM
GCC is decent and does tail-call optimisation.
So you can in general write your tail-recursive code in the most readable way. Thankfully.
Tobu, March 16, 2008 12:36 PM
why does C++ include the features of C that are known to be unsafe?
ajehandro, July 20, 2010 12:16 PM
Post a comment