This sounds really strange to me. So may I ask why? I find that recursion - most of the time - helps shorten and clarify the code. Also, doesn't recursion make induction proofs trivial?
The clearness and correctness of the code often ignores the possibility for stack overflow. Most naive implementations of DFS will hit the stack limit given trees that are all one long path from a single root to a single leaf.
1. Rule: Restrict all code to very simple control flow constructs – do not use goto statements, setjmp or longjmp constructs, and direct or indirect recursion.
Rationale: Simpler control flow translates into stronger capabilities for verification and often results in improved code clarity. The banishment of recursion is perhaps the biggest surprise here. Without recursion, though, we are guaranteed to have an acyclic function call graph, which can be exploited by code analyzers, and can directly help to prove that all executions that should be bounded are in fact bounded. (Note that this rule does not require that all functions have a single point of return – although this often also simplifies control flow. There are enough cases, though, where an early error return is the simpler solution.)
This is rule 1 of 10, so he apparently feels strongly about "banishing recursion." Gerard was formerly at Bell Labs and is also a fellow of the ACM and a member of the NAE.
In most systems lots of really important stuff is allocated at the bottom of the heap. It's very easy for a clobbered global flag (yes, hissss, globals, these are very constrained computers we're talking about here) to cause a system to have its shit get real at an alarming rate.
Also many of these systems where hard real time as in "if we don't respond in under 30ms something expensive goes bang" and again recursion can cause problems with that, lots of these systems are interrupt driven and have no garbage collection or threading so you can't just pre-empt them in that event since by the time you spot the problem you blew through your deadline and something went bang.
On the plus side you had a pretty good idea about how long the max processing would take (and avoid the timeouts and aforementioned "bang"), as the OS couldn't interrupt us. Certain system calls couldn't be made while in what we called "soft real time". Memory allocation was done upfront.
The process control of that system was interesting. You could assign processes to processors or groups of processors and then give those groups a scheduling method. I haven't seen anything like it in the years since I left.
If you assume infinite precision arithmetic and a very friendly environment for inputs, recursion always looks simpler, but by the time you clean it up to handle real world issues, non recursion instead looks simpler.
Its too easy to write recursive end conditions along the lines of "if x == 42" when your helpful floating point routine somehow mysteriously rounded x to 42.00000001 so it'll never equal, or "no (supposedly) UTF-16 encoded string would ever have an odd number of bytes, even though I have no control of the source and the source is known to occasionally be insane" or at least thats how I remember it. I've run into both. Its not funny at the time but in retrospect its usually fairly hilarious.
Personally I think its harder for people to understand concurrency issues WRT recursion, but I'll probably just get flamed for that one. I feel more people have "leveled up" with concurrency and non-recursive code and functional style programming than have leveled up to include recursion in that mix. Imagine two (three?) concurrent recursive algos fighting each other over one data structure.
If you are careful about test vectors, you can pseudo-exhaustively prove that an iterative dual to a recursive algorithm is equivalent.
This is very convenient in most cases, but could hide the fact that a direct recursive call will overflow your stack.
This isn't apparent and would test out ok until someone makes a small; seemingly insignificant change which the compiler can't do tail call optimization on, and all of a sudden things fail.