# Tail Call Optimization (TCO)

Tail Call Optimization (TCO) is a technique used by some compilers and interpreters to optimize recursive function calls. It allows a function to call itself without increasing the size of the call stack.

## 1. The Concept

In a standard recursive call, the computer must "remember" the current state (variables, return address) so it can come back to it after the recursive call finishes. This adds a new frame to the **Call Stack**.

If the recursive call is the **very last action** performed by the function (a "Tail Call"), there is no need to remember the current state because there is no work left to do in the current function.

*   **Optimization:** The compiler reuses the *current* stack frame for the next function call instead of creating a new one.
*   **Result:** Recursion becomes as memory-efficient as a loop ($O(1)$ space).

## 2. Standard vs. Tail Recursion

### Standard Recursion (Not Tail Recursive)
The multiplication happens *after* the recursive call returns. The stack must wait.

```python
def factorial(n):
    if n == 1: return 1
    return n * factorial(n - 1) # Pending operation: n * result
```

### Tail Recursion
The calculation happens *before* the call (in the accumulator). The return value is just the result of the next call.

```python
def factorial_tail(n, accumulator=1):
    if n == 1: return accumulator
    return factorial_tail(n - 1, n * accumulator) # No pending operation
```

## 3. Language Support

Not all languages support TCO.

*   **Functional Languages:** Heavily rely on recursion, so TCO is standard (Haskell, Elixir, Scheme).
*   **JavaScript (ES6):** The specification includes TCO, but browser support is inconsistent (Safari supports it, Chrome/Firefox often don't).
*   **JVM (Java):** Does not support TCO natively. Deep recursion will throw `StackOverflowError`.
*   **Python:** Does not support TCO. Guido van Rossum (creator) prefers clear stack traces over recursion optimization.
*   **Scala/Kotlin:** Run on JVM but offer compiler tricks (e.g., `@tailrec` in Scala) to convert tail recursion into a loop during compilation.

## 4. Why use it?

1.  **Safety:** Prevents Stack Overflow errors on large inputs.
2.  **Performance:** Reduces memory overhead.
3.  **Style:** Allows writing functional-style code (recursion) with the performance of imperative code (loops).

[[programming/recursion]]
[[programming/functional-programming]]
[[programming/stacks-and-queues]]