What is Tail Recursion?

Here you will learn about what is tail recursion with example.

Tail recursion refers to recursive call at last line. The tail recursive functions considered better as the recursive call is at the last statement so there is nothing left to do in the current function. It saves the current function’s stack frame is of no use.

Tail recursion can be eliminated by changing the recursive call to a goto preceded by a set of assignments per function call. This simulates the recursive call because nothing needs to be saved after the recursive call finishes. We can just goto the top of the function with the values that would have been used in a recursive call.

Image Source

The recursive function for Tower of Honoi Problem is given below. It is an example of recursive function with tail recursion.

Recursive Function TOH with Tail Recursion

void TOH(int n,char x,char y,char z)
{
	if(n>0)
	{
		TOH(n-1,x,z,y);
		printf("\n%c-> %c",x,y);
		TOH(n-1,z,y,x);		//tail recursion
	}
}

Without Tail Recursion

void TOH(int n,char x,char y,char z)
{
	char temp;
	label:
	if(n>0)
	{
		TOH(n-1,x,z,y);
		printf("\n%c-> %c",x,y);
		temp=x;
		x=z;
		z=temp;
		n=n-1;
		goto label;
	}
}