Re: need help Recursion and iteration...
[Prev][Next][Index][Thread]
Re: need help Recursion and iteration...
In article <75on9e$1kn$1@info3.fnal.gov>,
herber@dcdrjh.fnal.gov (Randolph J. Herber) wrote:
>
> 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));
> }
>
First off, to express a recursive function iteratively, you need
to be able to define/use dynamic structures. You'll have to
make up for the implicit return stack in recursion.
(Not for every problem of course eg the factorial)
It's been 10 years seen I've seen or done C coding, so be easy on
the syntax:
int A(int x, int y)
{
int S[],i;
S[1] := x;
S[2] := y;
i := 1;
while (i>0) do;
if S[i] = 0 then do; /* A(0,y) */
S[i] := S[i+1] + 1;
i := i - 1;
end;
else do;
if S[i+1] = 0 then do; /* A(x,0) */
S[i] := S[i] - 1;
S[i+1] := 1;
end;
else do; /* A(x,y) */
S[i+2] := S[i+1] - 1;
S[i+1] := S[i];
S[i] := S[i] - 1;
i := i + 1;
end;
end;
end;
return S[1];
}
I keep an array with an index, i. The index points at the current x, i+1
points at the current y.
Example for A(2,1):
i S
1 2 1
2 1 2 0
2 1 1 1
3 1 0 1 0
3 1 0 0 1
2 1 0 2
1 1 3
2 0 1 2
3 0 0 1 1
4 0 0 0 1 0
4 0 0 0 0 1
3 0 0 0 2
2 0 0 3
1 0 4
0 5
the answer is 5. The processing is identical to the recursive version.
Naturally in this case the recursive version is a lot easier to understand.
Believe me, it can ALWAYS be done.
--
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
References: