Is all non-tail recursion function convertible to tail recursion function?

[hui_yang]

Is all non-tail recursion function convertible to tail recursion function?

If not, what is the pattern of the non-tail recursion function which is not convertible to tail recursion function?

Is there any method to recognize whether a non-tail recursion function is convertible or not convertible to tail recursion function?

Thank you.

[hui_yang]

I search about the recursion function theory, there are article mentioned that there are 3 types of recursion function, which is
1)left-recursion
2)right-recursion
3)center nested recursion

and also, it state that the 3rd, center nested recursion is not convertible to tail-recursion function,
but how to recognize a center nested recursion function?

Thank You.

[tuffff]

I have never heard “center nested recursion” and googling yields 0 (!) results, so I cannot tell you how to recognise one.

But, you can transform every recursive function into a tail-recursive one by manually passing the call stack as an argument. If this has any advantage depends on the language, but usually I would say no.

Simple example: Return an in-order list of a simple binary tree (every node containing only a value and pointers to it’s children).

naïve recursion:

f(node):
  if (node == null)
    then return {}
    else return f(left-child(node)) ++ {value(node)} ++ f(right-child(node))

tail-recursion:

f(node):
  g({node}, {})
g(stack, result):
  node = stack[0]
  stack-tail = stack[1..]
  if (node == null)
    then return g(stack-tail, result)
  elseif (is-value(node))
    then return g(stack-tail, result ++ {node})
  else return g(left-child(node) . value(node) . right-child(node) . stack-tail, result)

I guess that, in about every “serious” language, the first one will perform better. Of course, you can optimise the second one further (e.g. avoid list-concatenations), but that was not the point I think :)

[Rashakil Fol]

But, you can transform every recursive function into a tail-recursive one by manually passing the call stack as an argument. If this has any advantage depends on the language, but usually I would say no.

This is actually not quite possible in every situation. Consider the following.

function go<T>() {
  if (doSomething<T>()) {
    go<Foo<T>>();
    doSomethingElse<T>();
  }
}

In many languages, you can't make a stack to represent the state of this function, without having to perform non-tail-recursive operations down the stack itself.

[arkoenig]

@tuff: I think that your statement solves the letter of the problem but violates its spirit. That is, I think the point of the original question was to understand which recursive functions could be turned into tail-recursive functions that in turn can be turned into iterative functions that require an amount of memory that is bounded even if the number of iterations is not bounded.

Otherwise, you can turn any recursive function into an iterative one by simulating the call stack yourself by hand.