45

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.

Eric Leschinski
  • 146,994
  • 96
  • 417
  • 335
Scarl
  • 950
  • 5
  • 16
  • 31
  • 4
    "Head recursion" isn't something I've ever heard of before. It doesn't sound like a useful concept; it's extremely rare for a recursive call to be the very first thing a function does. That precludes any sort of conditional to determine whether to execute the call and any arguments that would need to be evaluated before the function call. In some languages, it's even impossible, as the function must evaluate an expression at runtime to determine the function to recursively call. – user2357112 Jan 29 '14 at 09:25
  • Googled it. Looks like the sources that use the term have a very loose definition of "head", roughly meaning before the "real work". I'm not sure why they define "head recursion" at all; they don't seem to go anywhere with the concept. It definitely isn't as useful as tail recursion. – user2357112 Jan 29 '14 at 09:37
  • 1
    To differ between head recursion and everything that isn't tail recursion seems redundant. – Sylwester Jan 29 '14 at 11:44
  • @user2357112: pardon the late reply, but the difference between head recursion and tail recursion is important in that it can have memory implications. Anything calculated before the recursive call has to be stored in a stack until the entire subsequent recursive function is calculated. Certain systems require a more memory, and hence can't recurse as deeply and may error out, for tail recursion. Head recursion simply passes the function's result forward into the next iteration of calculations, so only 1 value ever needs to be stored at a time. – John Smith Jul 24 '18 at 21:39
  • 1
    @MichaelKupietz: You've got that backwards. Tail recursion can be optimized to eliminate indefinite call stack growth, and some functional programming languages make this mandatory. "Head recursion" needs to maintain call stack information, preventing such optimization. – user2357112 Jul 24 '18 at 22:27
  • @user2357112 Oops, don't know how I got them wrong. I must've had my head stuck up my tail. – John Smith Oct 12 '18 at 07:23
  • what's the point of head recursion anyways? why's it even a thing – csguy Jan 08 '20 at 05:21

1 Answers1

68

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.

VLAZ
  • 26,331
  • 9
  • 49
  • 67
Java Curious ღ
  • 3,622
  • 8
  • 39
  • 63
  • 3
    Umm... Tail Recursion is a seperate thing. Tail Call Optimisation is an optiisation that can be applied to tail recursion. They are not the same as implied in your first paragraph. – Sinkingpoint Jan 29 '14 at 09:21
  • 1
    Aren't these basically just the definitions the OP stated themselves? – Radiodef Jan 29 '14 at 09:28
  • 2
    Can one put an example for head recursion ? Because in my mind, having the first line of a method immediatly calling the recursion makes an infinite loop, no ? like int recurCall(int number) { int res = recurCall(number -1); ...process...; return res; }. – Julien Jan 29 '14 at 09:30
  • @Sara - I have given the difference in theory as well as with example. Look the paragraphs after the example it shows what you want. – Java Curious ღ Jan 29 '14 at 09:54
  • My Pleasure to help, Keep Smiling.. – Java Curious ღ Jan 29 '14 at 10:10
  • So is tail the same as post, and head the same as pre, recursion? –  Jul 05 '15 at 13:59