The variety of books, articles, blog posts suggests that rewriting recursive function into tail recursive function makes it faster. No doubts it is faster for trivial cases like generating Fibonacci numbers or calculating factorial. In such cases there is a typical approach to rewrite - by using "helper function" and additional parameter for intermediate results.

TAIL RECURSION is the great description of the differences between tail recursive and not tail recursive functions and the possible way how to turn the recursive function into a tail recursive one. What is important for such rewriting - the number of function calls is the same (before/after rewriting), the difference comes from the way how those calls are optimized for tail recursion.

Nevertheless, it is not always possible to convert the function into tail recursive one with such an easy trick. I would categorize such cases as below

1. Function still can be rewritten into tail recursive but that might require additional data structures and more substantial changes in the implementation
2. Function cannot be rewritten into tail recursive with any means but recursion still can be avoided by using loops and imitating stack (I'm not 100% sure that tail recursion is impossible in some cases and I cannot describe how identify such cases, so if there is any academical research on this subject - the link would be highly appreciated)

Now let me consider specific example when function can be rewritten into tail recursive by using additional structures and changing the way algorithm works.

Sample task: Print all sequences of length n containing 1 and 0 and which do not have adjacent 1s.

Obvious implementation which comes to mind first is below (on each step, if current value is 0 then we generate two sequences with length n-1 otherwise we generate only sequence with length n-1 which starts from 0)

  def gen001(lvl: Int, result: List[Int]):Unit = {
    //println("gen001")
    if (lvl > 0) {
      if (result.headOption.getOrElse(0) == 0) {
        gen001(lvl - 1, 0 :: result)
        gen001(lvl - 1, 1 :: result)
      } else gen001(lvl - 1, 0 :: result)
    } else {
      println(result.mkString(""))
    }
  }

  gen001(5, List())

It's not that straightforward to avoid two function calls when current element is 0 but that can be done if we generate children for each value in the intermediate sequences starting from the sequence '01' on the level 1. After having hierarchy of auxiliary sequences for level 1..n we can reconstruct the result (printResult) starting from leaf nodes (or sequence from the last iteration in other words).

  @tailrec
  def g001(lvl: Int, current: List[(Int, Int)], result: List[List[(Int, Int)]]):List[List[(Int, Int)]] = {
    //println("g001")
    if (lvl > 1) {
      val tmp = current.map(_._1).zipWithIndex
      val next = tmp.flatMap(x => x._1 match {case 0 => List((0, x._2), (1, x._2)) case 1 => List((0, x._2))})
      g001(lvl - 1, next, next :: result)
    } else result
  }

  def printResult(p: List[List[(Int, Int)]]) = {
    p.head.zipWithIndex.foreach(x => 
      println(p.scanLeft((-1, x._2))((r1, r2) => (r2(r1._2)._1, r2(r1._2)._2)).tail.map(_._1).mkString("")))
  }

  val r = g001(5, List(0,1).zipWithIndex, List(List(0,1).zipWithIndex))

  println(r)

  printResult(r)

Output

List(List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4), (0,5), (1,5), (0,6), (0,7), (1,7)), List((0,0), (1,0), (0,1), (0,2), (1,2), (0,3), (1,3), (0,4)), List((0,0), (1,0), (0,1), (0,2), (1,2)), List((0,0), (1,0), (0,1)), List((0,0), (1,1)))
00000
10000
01000
00100
10100
00010
10010
01010
00001
10001
01001
00101
10101

So now, if we compare two approaches, the first one requires much more recursive calls however on the other hand it's much more efficient in terms of memory because no additional data structures of intermediate results are required.

Finally, the questions are

1. Is there a class of recursive functions which cannot be implemented as tail recursive? If so how to identify them?
2. Is there a class of recursive functions such as their tail recursive implementation cannot be as efficient as non tail recursive one (for example in terms of memory usage). If so how to identify them. (Function from above example seems to be in this category)

Links to academical research papers are highly appreciated.

PS. Thera are a number of related questions already asked and below links may be quite useful

Rewrite linear recursive function as tail-recursive function

https://cs.stackexchange.com/questions/56867/why-are-loops-faster-than-recursion

CodePudding user response：

The class of functions in 1 is empty: any computable function written in a recursive style has a tail-recursive equivalent (at the limit, since there's a tail-recursive implementation of a Turing Machine, you can translate any computable function into a Turing Machine definition and then the tail recursive version of that function is running that definition through the tail-recursive implementation of a Turing Machine).

There are likewise no functions for which tail recursion is intrinsically less efficient than non-tail recursion. In your example, for instance, it's simply not correct that "it's much more efficient in terms of memory because no additional data structures of intermediate results are required." The required additional structure of intermediate results is implicit in the call-stack (which goes away in the tail recursive version). While the call stack is likely an array (more space efficient than a linked-list) it also, because of its generality, stores more data than is required.

CodePudding user response：

I would say that one clear example of a recursive function which cannot be implemented with tail-recursion is a function is one in which the last statement calls itself twice. One example would be a common recursive algorithm for finding the maximum depth of a binary tree, where the last line will look something like max(max_depth(left), max_depth(right)).