top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

what is tail recursion?

+5 votes
136 views

Please help me to understand the tail recursion with example.

posted Nov 22, 2013 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value. Since the current recursive instance is done executing at that point, saving its stack frame is a waste. Specifically, creating a new stack frame on top of the current, finished, frame is a waste. A compiler is said to implement TailRecursion if it recognizes this case and replaces the caller in place with the callee, so that instead of nesting the stack deeper, the current stack frame is reused. This is equivalent in effect to a "GoTo", and lets a programmer write recursive definitions without worrying about space inefficiency (from this cause) during execution. TailRecursion is then as efficient as iteration normally is.

Example
Consider this recursive definition of the factorial function in C:

  factorial(n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
  }

This definition is not tail-recursive since the recursive call to factorial is not the last thing in the function (its result has to be multiplied by n).

Tail Recursive version

  factorial1(n, accumulator) {
    if (n == 0) return accumulator;
    return factorial1(n - 1, n * accumulator);
  }

  factorial(n) {
    return factorial1(n, 1);
  }
answer Nov 22, 2013 by Luv Kumar
Similar Questions
+2 votes

I am looking for sample code which can impress an interviewer.

+4 votes

If we delete the mth number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4. If we delete the 3rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...