Sunday, February 15, 2015
What is Tail Recursion Example to Explain Tail Recursion
Tail recursion refers to recursive call at last line. 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.
The recursive function for Tower of Honoi Problem is given below. It is an example of recursive function with tail recursion.
Also Read: C Program for Tower of Hanoi Problem
Also Read: How to Convert a Recursive Function or Algorithm to Non-Recursive?
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("
%c -> %c",x,y);
%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("
%c -> %c",x,y);
%c -> %c",x,y);
temp=x;
x=z;
z=temp;
n=n-1;
goto label;
}
}
Watch below video to understand tail recursion easily.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.