On Jun 6, 1:40 pm, "zee 99" <[EMAIL PROTECTED]> wrote:
> hi
>
> learnt that a tail recursive algorithm can be converted to a non recursive
> one by merely using a while and a goto
>
> is it true for all class of recursive algorithms or just the tail recursive
> ones ...
All. In fact there are several languages that, at some point in
their evolution, didn't allow for recursion at all. At least,
not without some finagling on the programmers part.
FORTRAN,COBOL,FORTH,etc.
> if all recursive ones can be converted , then do we have a general procedure
> ???
A lot of recursive procedures can be manipulated into tail
recursion by altering the algorithm slightly, just because it
isn't written as a tail recursive function doesn't mean it
cannot be. Sometimes the function can be flipped on it's
head by using an accumulator, instead of waiting for the
result of the recursive call then doing something, you
calculate a partial result and pass it with the call
and then final answer is calculated at the base case.
As a silly, obvious example:
Length(list)
if (empty list) then 0 else 1 + Length(rest(list))
becomes:
LengthHelper(list,acc)
if (empty list) then acc else LengthHelper(rest(list),1 + acc)
Length(list)
LengthHelper(list,0)
If all else fails we cheat. Instead of relying on the
language to keep track of the recursion, keep the states
in some form of data structure. (i.e. stack,n-ary tree,etc.)
----
Geoff
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
