The difference between head & tail recursion [duplicate]
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.
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
.