Re:Making robust software: the “Mars Code” talk (2012)
by FLUX-YOU on Monday February 15, 2016 @10:15AM
(#11103747)
When you can't use recursion, what data structures/algorithms do you use in place of the common data structures that often use recursion? I'm thinking of stuff like trees and quicksort. Do they even need these things?
[ Parent
| on HN ]
Re:Making robust software: the “Mars Code” talk (2012)
by pieceof314 on Monday February 15, 2016 @10:25AM
(#11103809)
Loops. A recursive algorithm can be transformed into an iterative looping algorithm that uses a fixed stack of memory.
There's probably no change in the algorithms. They just use non-recursive versions.
Re:Making robust software: the “Mars Code” talk (2012)
by marcosdumay on Monday February 15, 2016 @11:01AM
(#11104013)
What's the gain? If you turn your recursive algorithm into an iterative one with a stack, you are sill subject to all the same problems.
They probably don't use trees and quicksort at all.
Re:Making robust software: the “Mars Code” talk (2012)
by ktRolster on Monday February 15, 2016 @11:14AM
(#11104104)
> What's the gain?
You can prove that you won't have a stack overflow. You can calculate the maximum depth of the stack at compile time, not runtime.
Re:Making robust software: the “Mars Code” talk (2012)
by marcosdumay on Monday February 15, 2016 @03:14PM
(#11105609)
Well, you can either prove that you won't have a stack overflow at the original program, or you can not guarantee that your new code will run out of stack space.
If you can calculate the size of the stack at compile time, you don't need to manually manage it.
Re:Making robust software: the “Mars Code” talk (2012)
by dclowd9901 on Monday February 15, 2016 @11:23AM
(#11104159)
Can't you also just pass a bit through the recursion that contains its depth, and halt the recursion if that number gets too high?
Re:Making robust software: the “Mars Code” talk (2012)
by ktRolster on Monday February 15, 2016 @11:30AM
(#11104199)
Yes, but that depends on making sure you get the programming logic correct, whereas with banning recursion outright, it can be tested automatically.
Re:Making robust software: the “Mars Code” talk (2012)
by adrianN on Monday February 15, 2016 @10:45AM
(#11103914)
Typically you don't use dynamic allocation, making trees much more tedious to implement. The usual data structure is a stack allocated constant size array.
But if you really have to use recursion, you can always simulate it with a loop and an explicit stack. This way it's also easy to bound the stack size.