Wiki improvements

Forum for discussion about the documentation project.
Post Reply
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

A potential new article #17 ?

About:
  • 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?
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Wiki improvements

Post by badidea »

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.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Wiki improvements

Post by dodicat »

The prize is a quicksort with no recursion and no artificial stack.
(The crt quicksort is a mixture of sorts so doesn't count)
integer
Posts: 408
Joined: Feb 01, 2007 16:54
Location: usa

Re: Wiki improvements

Post by integer »

fxm wrote:A potential new article #17 ?
About:
  • 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.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Wiki improvements

Post by paul doe »

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.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

Let's go!
See preamble at: Index page of tutorial / teaching / pedagogical topics (draft articles for documentation)

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.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Wiki improvements

Post by paul doe »

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
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

Okay.
Nevertheless, I set myself a goal of 2 weeks to release the article.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

@coderJeff,

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).

Should this be precised in the documentation?
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

fxm wrote:Okay.
Nevertheless, I set myself a goal of 2 weeks to release the article.
Long live retirement! 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.
coderJeff
Site Admin
Posts: 4313
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Wiki improvements

Post by coderJeff »

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. :)

Updated Operator New Expression. Please feel free to correct/add/change/etc.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

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.
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.
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Wiki improvements

Post by badidea »

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 :-)
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

fxm wrote:
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.
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)
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Wiki improvements

Post by fxm »

Another potential new article #18 ?

About:
  • How is array passed to FB procedure and what can procedure body do versus main body
I already wrote posts around this topic.
I could complete these and reword/synthesize all that in an article.

Would some people be interested in such an article?
Post Reply