Tail recursion vs head classic recursion

问题:

listening to Scala courses and explanations I often hear: "but in real code we are not using recursion, but tail recursion".

Does it mean that in my Real code I should NOT use recursion, but tail recursion that is very much like looping and does not require that epic phrase "in order to understand recursion you first need understand recursion" .

In reality, taking into account your stack.. you more likely would use loop-like tail recursion.

Am I wrong? Is that 'classic' recursion is good only for education purposes to make your brain travel back to the university-past?

Or, for all that, there is place where we can use it.. where the depth of recursion calls is less than X (where X your stack-overflow limit). Or we can start coding from classic-recursion and then, being afraid of your stack blowing one day, apply couple of refactorings to make it tail-like to make use even stronger on refactoring field?

Question: Some real samples that you would use / have used 'classic head' recursion in your real code, which is not refactored yet into tail one, maybe?

回答1:

Tail Recursion == Loop

You can take any loop and express it as tail-recursive call.

Background: In pure FP, everything must result in some value. while loop in scala doesn't result in any expression, only side-effects (e.g. update some variable). It exists only to support programmers coming from imperative background. Scala encourages developers to reconsider replacing while loop with recursion, which always result in some value.

So according to Scala: Recursion is the new iteration.

However, there is a problem with previous statement: while "Regular" Recursive code is easier to read, it comes with a performance penalty AND carries an inherent risk of overflowing the stack. On the other hand, tail-recursive code will never result in stack overflow (at least in Scala*), and the performance will be the same as loops (In fact, I'm sure Scala converts all tail recursive calls to plain old iterations).

Going back to the question, nothing wrong with sticking to the "Regular" recursion, unless:

1. The algorithm you are using in calculating large numbers (stack overflow)
2. Tail Recursion brings a noticeable performance gain

回答2:

The first thing one should look at when developing software is the readability and maintainability of the code. Looking at performance characteristics is mostly premature optimization.

There is no reason not to use recursion when it helps to write high quality code.

The same counts for tail recursion vs. normal loops. Just look at this simple tail recursive function:

def gcd(a: Int, b: Int) = {
  def loop(a: Int, b: Int): Int =
    if (b == 0) a else loop(b, a%b)
  loop(math.abs(a), math.abs(b))
}

It calculates the greatest common divisor of two numbers. Once you know the algorithm it is clear how it works - writing this with a while-loop wouldn't make it clearer. Instead you would probably introduce a bug on the first try because you forgot to store a new value into one of the variables a or b.

On the other side see these two functions:

def goRec(i: Int): Unit = {
  if (i < 5) {
    println(i)
    goRec(i+1)
  }
}

def goLoop(i: Int): Unit = {
  var j = i
  while (j < 5) {
    println(j)
    j += 1
  }
}

Which one is easier to read? They are more or less equal - all the syntax sugar you gain for tail recursive functions due to Scalas expression based nature is gone.

For recursive functions there is another thing that comes to play: lazy evaluation. If your code is lazy evaluated it can be recursive but no stack overflow will happen. See this simple function:

def map(f: Int => Int, xs: Stream[Int]): Stream[Int] = f -> xs match {
  case (_, Stream.Empty) => Stream.Empty
  case (f, x #:: xs)     => f(x) #:: map(f, xs)
}

Will it crash for large inputs? I don't think so:

scala> map(_+1, Stream.from(0).takeWhile(_<=1000000)).last
res6: Int = 1000001

Trying the same with Scalas List would kill your program. But because Stream is lazy this is not a problem. In this case you could also write a tail recursive function but generally this not easily possible.

There are many algorithms which will not be clear when they are written iteratively - one example is depth first search of a graph. Do you want to maintain a stack by yourself just to save the values where you need to go back to? No, you won't because it is error prone and looks ugly (beside from any definition of recursion - it would call a iterative depth first search recursion as well because it has to use a stack and "normal" recursion has to use a stack as well - it is just hidden from the developer and maintained by the compiler).

---

To come back to the point of premature optimization, I have heard a nice analogy: When you have a problem that can't be solved with Int because your numbers will get large and it is likely that you get an overflow then don't switch to Long because it is likely that you get an overflow here as well.

For recursion it means that there may be cases where you will blow up your stack but it is more likely that when you switch to a memory only based solution you will get an out of memory error instead. A better advice is to find a different algorithm that doesn't perform that badly.

---

As conclusion, try to prefer tail recursion instead of loops or normal recursion because it will for sure not kill your stack. But when you can do better then don't hesitate to do it better.

回答3:

If you're not dealing with a linear sequence, then trying to write a tail-recursive function to traverse the entire collection is very difficult. In such cases, for the sake of readability/maintainability, you usually just use normal recursion instead.

A common example of this is a traversal of a binary tree data structure. For each node you might need to recur on both the left and right child nodes. If you were to try to write such a function recursively, where first the left node is visited and then the right, you'd need to maintain some sort of auxiliary data structure to track all the remaining right nodes that need to be visited. However, you can achieve the same thing just using the stack, and it's going to be more readable.

An example of this is the iterator method from Scala's RedBlack tree:

def iterator: Iterator[(A, B)] =
  left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator

回答4:

There are two basic kinds of recursion:

1. head recursion
2. Tail recursion

In head recursion, a function makes its recursive call and then performs some more calculations, maybe using the result of the recursive call, for example. In a tail recursive function, all calculations happen first and the recursive call is the last thing that happens.

The importance of this distinction doesn’t jump out at you, but it’s extremely important! Imagine a tail recursive function. It runs. It completes all its computation. As its very last action, it is ready to make its recursive call. What, at this point, is the use of the stack frame? None at all. We don’t need our local variables anymore because we’re done with all computations. We don’t need to know which function we’re in because we’re just going to re-enter the very same function. Scala, in the case of tail recursion, can eliminate the creation of a new stack frame and just re-use the current stack frame. The stack never gets any deeper, no matter how many times the recursive call is made. That’s the voodoo that makes tail recursion special in Scala.

Let's see with the example.

 def factorial1(n:Int):Int =
     if (n == 0) 1 else n * factorial1(n -1)


 def factorial2(n:Int):Int = {
      def loop(acc:Int,n:Int):Int =
           if (n == 0) 1 else loop(acc * n,n -1)

     loop(1,n)  
  } 

Incidentally, some languages achieve a similar end by converting tail recursion into iteration rather than by manipulating the stack.

This won’t work with head recursion. Do you see why? Imagine a head recursive function. First it does some work, then it makes its recursive call, then it does a little more work. We can’t just re-use the current stack frame when we make that recursive call. We’re going to NEED that stack frame info after the recursive call completes. It has our local variables, including the result (if any) returned by the recursive call.

Here’s a question for you. Is the example function factorial1 head recursive or tail recursive? Well, what does it do? (A) It checks whether its parameter is 0. (B) If so, it returns 1 since factorial of 0 is 1. (C) If not, it returns n multiply by the result of a recursive call. The recursive call is the last thing we typed before ending the function. That’s tail recursion, right? Wrong. The recursive call is made, and THEN n is multiplied by the result, and this product is returned. This is actually head recursion (or middle recursion, if you like) because the recursive call is not the very last thing that happens.

For more info please refer the link