What is tail recursion? Give an example.

0 votes
asked in Interview Question by admin
What is tail recursion? Give an example.
Add question to:

1 Answer

+1 vote
answered by admin
 
Best answer

Tails recursive functions are recursive functions where there is no further computation after the recursive statement call.

Example: In this example, you can see there is no computation left in fun(n) function after fun(n-1) call

void fun(int n){
if(n==1)
  printf("1");
else
  fun(n-1);
}

Non tail recursive function: You can easily check that we need to multiply n with the result of recursive call fun(n-1) 

int fun(int n){
if(n==1)
  return 1;
else
  return n*fun(n-1);
}

Why we care about tail recursive functions:

To understand this you should know that every function call has a stack frame where the intermediate values of function’s variables are stored.Like for fun(4) call n=4 is stored and n=5 for fun(5).So in the recursive call, these frames are kept in memory until all the computation finished.So in tail recursion, we don’t need to keep these frames as we know there is no computation done after the call to the recursive statement.So this optimizes the space.

...