News for hackers. Stuff that matters.
Re:How recursion got into programming: a comedy of errors by PaulHoule on Wednesday July 23, 2014 @07:48AM (#8073817)
Recursion isn't allowed for safety critical code in automotive or avionics applications

http://spinroot.com/p10/rule1.html

Re:How recursion got into programming: a comedy of errors by Retric on Wednesday July 23, 2014 @09:26AM (#8074225)
The rational is vary reasonable. Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory. However, tail call optimization is basically the compiler doing that conversion for you which also removes the risks.
Re:How recursion got into programming: a comedy of errors by pmahoney on Wednesday July 23, 2014 @09:51AM (#8074330)
Well, if the compiler will also report error for recursive calls not in tail position...

There are strategies to prove various things about recursive calls. See Ada/Spark's explanation for Rule 17.2 in [1].

I'm not familiar with Coq and Agda, but I believe they allow recursive calls if they can prove termination, though "termination" may be different than "using too much stack".

[1] http://www.spark-2014.org/entries/detail/misra-c-2012-vs-spa...

Re:How recursion got into programming: a comedy of errors by Tyr42 on Wednesday July 23, 2014 @03:41PM (#8076517)
As a rule of thumb, they permit recursion where one parameter "obviously" is getting smaller each time, with a base case at 0 or the empty list or whatever.

You can annotate the program in ways to make the compiler see that a parameter is actually getting smaller.

Re:How recursion got into programming: a comedy of errors by chriswarbo on Wednesday July 23, 2014 @10:21AM (#8074482)
Replacing recursion with a loop can easily use extra memory. The usual approach is to implement a stack using a local variable: each iteration pops the head and processes it; rather than recursing, we push a new item and let the next iteration process it for us.

If the algorithm is tail-recursive, this will use constant stack space and memory, just like tail-call optimisation. If the algorithm's not tail-recursive, it will use constant stack space but large (potentially exponential) amounts of memory.

There's no way around this. The only solution is to come up with a different algorithm (eg. using an accumulator).

Re:How recursion got into programming: a comedy of errors by to3m on Wednesday July 23, 2014 @04:37PM (#8076821)
You're usually better off with manual recursion, if you're concerned about running out of space, for the simple reason that it's far easier in practice to back out of an out-of-memory situation than from a stack overflow.
Re:How recursion got into programming: a comedy of errors by Retric on Wednesday July 23, 2014 @01:03PM (#8075470)
Optimal loops don't use more memory than recursion and generally significantly less. Though if you can find an counter example in a common programming language I would love to see it.

However, we are talking about the automotive and aerospace industry so recursion overhead is often a deal breaker even if there are no other issues.

Re:How recursion got into programming: a comedy of errors by theseoafs on Wednesday July 23, 2014 @09:51PM (#8077869)
> Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory.

This isn't true at all. You can replace all recursion with loops, sure, but you're going to have to simulate a stack (i.e. use extra memory) to convert complex recursive functions to loops.

Re:How recursion got into programming: a comedy of errors by exo762 on Thursday July 24, 2014 @05:01AM (#8078723)
I believe that there is a better reason to ban recursion - it may mask possible execution time of code. Loops are more explicit in that regard. If you are writing a real-time system, you care about those things a lot. Ban of dynamic memory also may be caused by requirement to be real-time.
Re:How recursion got into programming: a comedy of errors by liotier on Wednesday July 23, 2014 @09:41AM (#8074282)
> tail call optimization is basically the compiler doing that conversion for you which removes the risks.

Then can one argue that loops vs. recursion is mostly a matter of style and loops just as good as recursion since the compiler will optimize them that way anyway ?

Re:How recursion got into programming: a comedy of errors by axman6 on Wednesday July 23, 2014 @09:39PM (#8077847)
Not all recursive functions can be rewritten to be non-recursive. The Ackerman function is one such example. It's clearly tail recursive, but not only tail recursive so it must use some kind of stack or tree or something which isn;t linear like a loop. there's some explanation on the Computerphile youtube channel discussing it: https://www.youtube.com/watch?v=Mv9NEXX1VHc
Re:How recursion got into programming: a comedy of errors by dspillett on Wednesday July 23, 2014 @09:54AM (#8074349)
Yes, but only in the cases where the tail recursion optimisation is applicable.

Recursive constructs are can be not tail recursive (and usually are with new starter developers) and many languages ignore it anyway (meaning even code that can be unpacked from function calls into a loop are not so the stack is still used).

Re:How recursion got into programming: a comedy of errors by rubiquity on Wednesday July 23, 2014 @09:55AM (#8074350)
Yes, but humans mess up loops far more frequently than compilers do. If we follow your argument recursively, we would all end up writing assembly language again, wouldn't we? :)
Re:How recursion got into programming: a comedy of errors by coldtea on Wednesday July 23, 2014 @10:42AM (#8074602)
Is that meant as an argument against loops and pro recursion?

Because humans also screw recursion all the time.

Re:How recursion got into programming: a comedy of errors by rubiquity on Wednesday July 23, 2014 @11:00AM (#8074689)
I guess. But if I make the mistake of infinitely recursing I find out the next time I run my program. If I'm writing my own loops and make an off by one error it could go uncaught potentially forever.
Re:How recursion got into programming: a comedy of errors by pekk on Wednesday July 23, 2014 @12:24PM (#8075193)
You don't necessarily find out the next time you run your program. A stack overflow can go uncaught potentially forever.
Re:How recursion got into programming: a comedy of errors by PaulHoule on Wednesday July 23, 2014 @12:48PM (#8075354)
One of my favorite PHP gotchas is to accidentally write a function that calls itself infinitely, and then have the interpreter die without a warning message.
Re:How recursion got into programming: a comedy of errors by mtdewcmu on Thursday July 24, 2014 @12:09AM (#8078178)
If a program is only doing a simple calculation and it's still running an hour later, you should probably suspect an infinite loop and not wait for it to stop.
Re:How recursion got into programming: a comedy of errors by Rusky on Wednesday July 23, 2014 @02:13PM (#8075937)
So use iterators? Sometimes loops are just the clearer way to express something.
Re:How recursion got into programming: a comedy of errors by pjmlp on Thursday July 24, 2014 @02:25AM (#8078374)
Dynamic memory allocation is also banned.