CODEWITHSUNDEEP
recursiontail-recursionlambda-calculus
PDani
PDani

Reputation: 735

General recursion to tail-recursion

Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.

My view is that it's not possible everytime. For example if you have a function which calls itself recursively twice or three times, then you can't make all the recursive calls into tail-calls, right? Or is there always a way to reduce the number of recursive calls to one single recursive call?

Upvotes: 2

Views: 93

Answers (1)

Sylwester
Sylwester

Reputation: 48745

No. If you cannot rewrite your algorithm to have only tail calls, like in tree traversal, at least one call will not be in tail position.

Some may say loop + explicit stack is iterative, but IMO it's still recursion and a tree traversal will grow the stack just as general recursion.

Upvotes: 0

Related Questions