The difference between head & tail recursion [dupl

问题:

This question already has an answer here:

• What is tail recursion? 24 answers

I'm trying to get the difference between these 2 recursive strategies.

The definition I was told is the following:

Tail Recursion: A call is tail-recursive if nothing has to be done after the call returns i.e. when the call returns, the returned value is immediately returned from the calling function

Head Recursion: A call is head-recursive when the first statement of the function is the recursive call.

回答1:

In head recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function).

In tail recursion, it’s the opposite—the processing occurs before the recursive call. Choosing between the two recursive styles may seem arbitrary, but the choice can make all the difference.

A function with a path with a single recursive call at the beginning of the path uses what is called head recursion. The factorial function of a previous exhibit uses head recursion. The first thing it does once it determines that recursion is needed is to call itself with the decremented parameter. A function with a single recursive call at the end of a path is using tail recursion. Refer this article

Example Recursion :

public void tail(int n)         |     public void head(int n)
{                               |     {
    if(n == 1)                  |         if(n == 0)
        return;                 |             return;
    else                        |         else
        System.out.println(n);  |             head(n-1);
                                |
    tail(n-1);                  |         System.out.println(n);
}                               |     }

If the recursive call occurs at the end of a method, it is called a tail recursion. The tail recursion is similar to a loop. The method executes all the statements before jumping into the next recursive call.

If the recursive call occurs at the beginning of a method, it is called a head recursion. The method saves the state before jumping into the next recursive call.