top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

what is tail recursion?

+5 votes
366 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.

...