Re: need help Recursion and iteration...
[Prev][Next][Index][Thread]
Re: need help Recursion and iteration...
In article <75nj88$o88$1@nnrp1.dejanews.com>,
<werner_huysegoms@my-dejanews.com> wrote:
>In article <367d657d.20892851@news1.qc.sympatico.ca>,
> bmorrissNOSPAM@sympatico.ca (Benoit Morrissette) wrote:
>> But there
>> exists some classes of algorythmic problems that can be solved
>> only through recursion ( graphs and trees ).
He's right.
>Er.. no. Every recursive program may be written in iterative form.
>It's not always trivial (as with the factorial), but it can be done.
He's wrong.
Ackermann's function is a counterexample.
int A(int x, int y)
{
if(x == 0) return y + 1;
else if(y == 0) return A(x-1,1);
else return A(x-1,A(x,y-1));
}
See also: http://www.astro.virginia.edu/~eww6n/math/AckermannFunction.html
>> And in many
>> cases, recursion leads to programs that are more readable,
>> easier to debug and faster to write at the cost of using
>> more memory and taking more time to run.
>I second that.
>Best Regards,
>Werner Huysegoms
>Reply-To: werner.huysegoms@dgx11.cec.be
>remove the x before replying
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Randolph J. Herber, herber@dcdrjh.fnal.gov, +1 630 840 2966, CD/CDFTF PK-149F,
Mail Stop 318, Fermilab, Kirk & Pine Rds., PO Box 500, Batavia, IL 60510-0500,
USA. (Speaking for myself and not for US, US DOE, FNAL nor URA.) (Product,
trade, or service marks herein belong to their respective owners.)
Follow-Ups:
References: