Wiki improvements

Forum for discussion about the documentation project.
fxm
Posts: 8424
Joined: Apr 22, 2009 12:46
Location: Paris (suburbs), FRANCE

Re: Wiki improvements

Postby fxm » Sep 15, 2018 13:55

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: 1004
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Wiki improvements

Postby badidea » Sep 15, 2018 14:46

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: 5225
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Wiki improvements

Postby dodicat » Sep 15, 2018 20:56

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: 373
Joined: Feb 01, 2007 16:54
Location: usa

Re: Wiki improvements

Postby integer » Sep 17, 2018 16:51

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
Posts: 803
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Wiki improvements

Postby paul doe » Sep 18, 2018 3:05

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

Re: Wiki improvements

Postby fxm » Sep 18, 2018 9:15

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
Posts: 803
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Wiki improvements

Postby paul doe » Sep 18, 2018 9:32

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

Re: Wiki improvements

Postby fxm » Sep 18, 2018 9:51

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

Re: Wiki improvements

Postby fxm » Sep 21, 2018 5:17

@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
Posts: 8424
Joined: Apr 22, 2009 12:46
Location: Paris (suburbs), FRANCE

Re: Wiki improvements

Postby fxm » Sep 21, 2018 12:08

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: 2717
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Wiki improvements

Postby coderJeff » Sep 22, 2018 16:08

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

Re: Wiki improvements

Postby fxm » Sep 22, 2018 20:08

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: 1004
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Wiki improvements

Postby badidea » Sep 22, 2018 22:09

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

Re: Wiki improvements

Postby fxm » Sep 25, 2018 19:59

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

Re: Wiki improvements

Postby fxm » Oct 08, 2018 9:39

Another potential new article #18 ?

About:
    How is an array passed to an FB procedure and what can procedure body do with it 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?

Return to “Documentation”

Who is online

Users browsing this forum: No registered users and 0 guests