Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can all recursive functions be re-written as tail-recursions? [duplicate]

Tags:

Possible Duplicate:
Are there problems that cannot be written using tail recursion?

From my understanding, tail recursion is an optimization you can use when a recursive call does not need information from the recursive calls that it will spam.

Is it possible then to implement all recursive functions using tail-recursion? What about something like DFS, where you need the innermost child to return before the parent can?

like image 433
aerain Avatar asked Jul 30 '12 03:07

aerain


People also ask

Can all recursive functions be rewritten as loops?

So, yes all-recursive code can be converted to iteration.

Can every recursion be Memoized?

The short answer is: Yes. However, there are some constraints. The most obvious one is that recursive calls must overlap. I.e. during the execution of an algorithm, the recursive function must be called multiple times with the same parameters.

What can be used to replace tail recursion?

This is the case with, so called, tail recursions. Tail recursions are recursions where the recursive call is the last line in the method. Tail recursions are generally considered a bad practice and should be replaced with Iteration. This technique is well known to the people who work on compiler implementations.

Can a recursion function always be replaced by iteration?

Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program.


2 Answers

It depends on exactly what you are asking.

If you want to keep all functions as functions (no mutable state) with the same signatures, then no. The most obvious example is the quicksort, where both calls can't be tail calls.

If you can modify the function in various ways, then yes. Sometimes a local modification is sufficient - often you can add an "accumulator" that builds some expression that is returned, although, if the result involves non-commutative operations, then you need to be careful (for example, when naively constructing linked lists, the order is reversed) or you can add a stack.

Alternatively, you can do a global modification of the entire program, in which each function takes as an extra argument the function that contains future actions. This is the continuation passing that Pete is talking about.

if you are working by hand then the local modification is often fairly easy. but if you're doing automated rewriting (in a compiler for example) then it's simpler to take the global approach (it requires less "smarts").

like image 69
andrew cooke Avatar answered Nov 12 '22 22:11

andrew cooke


Yes and no.

Yes, used in conjunction with other control flow mechanisms (e.g., continuation passing) you can express any arbitrary control flow as tail recursion.

No, it is not possible to express all recursion as tail recursion unless you do supplement the tail recursion with other control flow mechanisms.

like image 39
Jerry Coffin Avatar answered Nov 12 '22 22:11

Jerry Coffin