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

Question

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

Answer 1

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.