hey, guys now we are gonna look at what is tail recursion and non-tail recursion. what is the difference between them and which is best to use?
Recursion is the calling the function itself is called recursion.we all are familiar with this normal recursion.
write a recursive function to print numbers from 1 to n
void fun(int n)
if (n<1) return; fun(n-1); cout << " " << n;}
Tail recursion is the last thing that executed by the function called tail-recursive function. In tail-recursion, you do not need to store the state of a child’s value whereas in case of non-tail recursion the child’s value is passed to the parent then the values can be calculated. Let’s understand this clearly with a small example.
why tail-recursion is best?
The tail-recursive functions considered better than non-tail recursive functions as tail-recursion can be optimized by the compiler. The idea used by compilers to optimize tail-recursive functions is simple since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.
Can we write a non-tail recursive function in tail-recursive function?
tail-recursive function to print numbers from n to 1
// An example of tail recursive function
//program to print numbers from the n to 1
void fun(int n)
if (n==0) return;
cout << " " << n;
// The last executed statement is tail recursive call
fun(n-1); //there are no statements to be executed after this.
we have already written a recursive function to print numbers from 1 to n
let’s write the same recursive function in the tail-recursive function. Hey stop here before going into that let’s take pen and paper and try writing on your own the tail-recursive function to print numbers from 1 to n by observing the above example.
//tail recursive function to print numbers from 1 to n
void fun(int n; k=1)
if (n<1) return;
cout << " " <<k;
// The last executed statement is recursive call
it’s time to test you
given the factorial function
int fact(int n)
Re-write the above factorial function as Tail-recursion.first try on your own .
here we go
int fact(int n,value =1)
I hope you learn about tail-recursion.