Tail Recursion

Tail Call vs Non-tail Call

Equivalence of Tail Recursion and Iteration

Key Takeaway

Tail Recursion and Iteration are Equivalent: Any algorithm that can be implemented with iteration (loops) can also be implemented with tail recursion, and vice versa. Smart compilers optimize tail recursive code to execute similarly to iterative code.

Summary: Equivalence of Tail Recursion and Iteration

Similarities Between Tail Recursion and Iteration

• Behavior: Both iterative and tail-recursive implementations of an algorithm behave similarly.
• Execution: With tail recursion elimination, tail-recursive functions reuse the same stack frame, just like iterative functions reuse the same loop context.

Iterative Implementation Example

Iterative Factorial Function:

int factorial(int n) {
  int ans = 1;
  while (n > 0) {
    ans = ans * n;
    n--;
  }
  return ans;
}

• Initialization: int ans = 1;
• Loop: while (n > 0)
  • Multiply ans by n.
  • Decrement n.

Tail-Recursive Implementation Example

Tail-Recursive Factorial Function:

int factorial_helper(int n, int acc) {
  if (n <= 0) {
    return acc;
  }
  return factorial_helper(n - 1, n * acc);  // Tail call
}

int factorial(int n) {
  return factorial_helper(n, 1);  // Initial call with accumulator
}

• Helper Function: factorial_helper with parameters n and acc.