what is tail recursion?

Question

Please help me to understand the tail recursion with example.

Answer 1

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);
  }