Re: newbie question: recursion algorithm and iterative algorithm

From: Matthew Huntbach (mmh_at_dcs.qmw.ac.uk)
Date: 02/10/04 

Date: 10 Feb 2004 16:37:41 GMT

Norbert E. Fuchs <fuchs@ifi.unizh.ch> wrote:
> In article <3f349ddf.0402100313.4fb1d20b@posting.google.com>,
> chenyu468@yahoo.com (chenyu) wrote:
 
>> "In addition he says that every recursion algorithm can be translated
>> into iterative algorithm." <==== right??
>>
>>
>> I don't whether there exists an easy transform algorithm to do the
>> translation job or not. Or the existance is proved but transform
>> depends on everyone's technique and knowledge.
>>
>> Could you explain it to me?
 
> Concerning the transformation "recursion" -> "iteration" look for "tail
> recursion optimisation" in a Prolog textbook, for instance Sterling &
> Shapiro.

Prolog doesn't have iteration. Iteration requires a mutable state,
which Prolog doesn't have. Of course, you can model iteration by tail
recursion in Prolog, and the implementation may implement it by iteration.
But conceptually, it's still recursion, and I doubt the novice programmer
will see it as anything but recursion.

The answer to chenyu's question is that if you're using Prolog, no,
recursion cannot be translated to iteration because Prolog doesn't
have iteration.

But more subtlely, recursion can be converted to iteration by making
implicit the stack which is implicit in a sequence of recursive
calls. So the professor was right, recursive algorithms can always
be converted to iterative algorithms. In practice you can do the same
in Prolog providing you have the ability to visualise tail recursion as
iteration.

Matthew Huntbach

Relevant Pages

  • Re: CoBOL moved to OO
    ... > there algorithms that can be coded more easily as recursive expressions versus ... > algorithm in recursion and not think it in iteration and that is why the ...
    (comp.lang.cobol)
  • Re: newbie question: recursion algorithm and iterative algorithm
    ... >> Prolog doesn't have iteration. ... > That depends a bit on how you define iteration. ... I'm taking the view of the novice programmer who asks "Can recursion ... > In fact, in programming language semantics, one usually treats iteration ...
    (comp.lang.prolog)
  • Re: newbie question: recursion algorithm and iterative algorithm
    ... > Prolog doesn't have iteration. ... That depends a bit on how you define iteration. ... in the sense that it can be expressed in the form of tail recursion. ... In fact, in programming language semantics, one usually treats iteration ...
    (comp.lang.prolog)
  • Re: Grammatical Recursion
    ... >> One can only talk about the difference between recursion and ... >> iteration in the context of specific computation models. ... Shifting the topic from the algorithms themselves ...
    (sci.lang)
  • Re: Software bugs arent inevitable
    ... also invalid when 'iteration' and 'recursion' are reversed, no matter how often repeated in texts and articles. ... Some algorithms require much more mental effort to understand when in their recursive form versus the iterative form, ...
    (comp.lang.python)
Loading