Could be interesting. The main advantages over recursion is speed and 'no' memory limit?
I once wrote a non-recursive flood-fill because of these advantages. Later, I learned that there are are efficient filling algorithms however.
Last edited by badidea on Sep 15, 2018 21:35, edited 1 time in total.
How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB
I already wrote a thread around this topic.
I could complete it and reword/synthesize all that in an article.
Would some people be interested in such an article?
YES.
Any clarification might remove the fog or help me create a proper question about recursion/iteration.
fxm wrote:...
Would some people be interested in such an article?
Yes, I think it'll be useful. I was considering starting a thread to talk about several different data structures, possible implementation issues (not all of them are trivially easy to implement), and how to use them. I think that the article you propose can serve as a good introductory course on the subject.
But it will take me some time to clearly describe how to move from a recursive implementation ("tail" / not "tail") to an iterative implementation ("simple" / "more complex" with its own storage stack).
This process represents the essence of the article, because in my opinion not or little explained clearly in the literature.
fxm wrote:But it will take me some time to clearly describe how to move from a recursive implementation ("tail" / not "tail") to an iterative implementation ("simple" / "more complex" with its own storage stack).
Take all the time you need, nobody will hurry you =D
About your last update of the Operator New Expression page:
- the extra uinteger that stores the number of elements allocated (as part of the allocation) is added by New[] for the Types with destructors (explicit or implicit),
- for the Types with no destructor, New[] allocates only the required memory size requested by the number of elements to allocate (without extra uinteger).
It may be a somewhat dense article but I have tried to be clear and precise at the same time, with many examples illustrating step by step the process of translating a recursive form into an iterative form.
fxm wrote:- the extra uinteger that stores the number of elements allocated (as part of the allocation) is added by New[] for the Types with destructors (explicit or implicit)
I forgot this. I should not write documentation past my bed-time. :)
It may be a somewhat dense article but I have tried to be clear and precise at the same time, with many examples illustrating step by step the process of translating a recursive form into an iterative form.
However I added an example, the famous "tower of Hanoi algorithm" where the translation of the recursive form into iterative form is less easy, but this still results in a short iterative code.
Note: I am surprised not to find such an iterative code with stacking for the Hanoi Tower in the literature, where I often see only iterative codes that are long, awful, and twisted.
fxm wrote:It may be a somewhat dense article but I have tried to be clear and precise at the same time, with many examples illustrating step by step the process of translating a recursive form into an iterative form.
I skipped most of the text and starting reading and playing with the code in section 2.2 :-)
It may be a somewhat dense article but I have tried to be clear and precise at the same time, with many examples illustrating step by step the process of translating a recursive form into an iterative form.
However I added an example, the famous "tower of Hanoi algorithm" where the translation of the recursive form into iterative form is less easy, but this still results in a short iterative code.
Note: I am surprised not to find such an iterative code with stacking for the Hanoi Tower in the literature, where I often see only iterative codes that are long, awful, and twisted.
I added a last example (after the Hanoi tower), and I have a little optimized (for execution time) the macro for user storage stack.
(plus some points of detail)