Understanding Recursion

Head & Tail Recursion:

A Recursive function typically perform some task and call the recursive function.

If a recursive call is made before the function performs its own task, then it is called Head-recursion. (Recursion is performed at the head of the function body).

In the Above Example, In funciton Sum(3) a call to recursive function Sum(2) will be made first and then the return value from Sum(2) will be added with n. This makes the function Sum, a head-recursive function.

Tip: In C language the order of e valuation of operands for operator + is not defined. It means that in the below statement (where x is an int variable and fun1 and fun2 are functions returning int):

x = fun1() + fun2();

whether fun1 will be called first or fun2 is not defined in the language. This has to be defined by the compiler.

A call to a recursive function is tail-recursive if it is made at the end of the function (after the function performs its own tasks).

Just to see the difference, consider the recursive function to traverse a link list:

If the below link list is send as an input to the above two funcitons:

then the outputs will be:

Head Recursion: 4  3  2  1 (Print the list in reverse order)

Tail Recursion: 1  2  3  4 (Print the list in forward order)

A tail-recursion is very easy to write in the form of a loop. So there should ideally be no reason to write a tail recursion in the code unless you are writing to demonstrate tail-recursion itself. (At least I don’t see any convincing example).

 
Next: Mixed Recursions …