Is it beneficial to convert recursion to tail recursion? [duplicate]

If it is beneficial, then how Big-O (time complexity) is affected? Embedded link provided by members does not answer original question.

• Recursion is very expensive no. [Recursion] is poorly supported by many popular programming languages name three. Dec 22 '17 at 8:10
• @greybeard where you guys are located? and what type of answers you guys provide? for an example you allow "What is tail recursion?" as a question on stackexchange and people are happily answering it. That question can be found on internet and millions of books around. Why you don't answer YES or NO or One liner in that why of question? link Dec 22 '17 at 9:51
• @greybeard one of them is python Dec 22 '17 at 9:54
• where you guys are located you can inspect each user's profile: some fill in enough to qualify for autobiographer, some know data avoidably disclosed to pose a risk. what type of answers you guys provide best stick with How do I write a good answer? - have a look at most voted for (and against: jump to end). Dec 23 '17 at 9:47
• you allow well, StackExchange is community moderated, with automatisms and extra responsibilities. I think it liberal: there is explicit ban - "everything" else is admissible, while not necessarily welcome. There are diverse fori: there is SO ("programming"), Theoretical Computer Science - this is CS, with, e.g, a difference between a programming language, its available & possible implementations. Dec 23 '17 at 10:16

Any recursion can be converted into tail recursion by transforming the function into continuation-passing style.

The continuations being built can be defunctionalized (a-la John C. Reinolds) into a list of custom data expressing the same intent.

In other words you gradually build a TODO list while going along, then you DO it. And while doing the topmost recorded task, you may add some more TODO tasks there.

But you never recurse, all you do is build and interpret the TODO data. The accumulator transform is a specific case of this.

The answer on the linked (as duplicate) question talks about the CPS. Here's the example from there, in Scheme/Lisp, with a little twist:

(lambda (a b c d)          ; a normal function of 4 arguments
(+ (- a b) (* c d)))


This could be transformed into continuation-passing style as follows:

(lambda (k a b c d)        ; the same, as a CPS-function,
(k- (lambda (v1)            ; expecting one additional function,
(k* (lambda (v2)       ; the "continuation" to be called
(k+ k v1 v2))
c d))
a b))


The twist is simply the naming of the CPS built-in functions, to remove possible confusion: while - is the regular subtraction function, k- is its CPS equivalent.

Every CPS-function accepts an additional parameter: a "continuation" function of one argument describing "what-to-do-next" with that argument.

So if - expects two arguments, to subtract one from the other, k- expects three arguments: in addition to the two values it expects a function of one argument that it will feed the result of the subtraction to.

As you can see, there's no recursion - the function itself is even unnamed. We construct big nested anonymous function instead, describing the future computation step by step in the typically inside-out linearized fashion.

• Any recursion can be converted into tail recursion by can you point me to elaborations for, say, quicksort and Ackermann? Dec 22 '17 at 18:16
• @greybeard non-in-place quicksort is just a treesort so should be straightforward to handle, with logarithmic simulated "stack". as for Ackermann, the size will be substantial but it shouldn't change anything. this is not about turning a recursive process into an iterative one; just about simulating the stack on the heap. Dec 22 '17 at 19:00
• the call stack, that is. Dec 23 '17 at 13:14