Can all recursive functions be re-written as tail-recursions?

recursion

tail-recursion

functional programming

computer science

algorithms

Can all recursive functions be re-written as tail-recursions?

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Yes, any recursive function can be mechanically transformed into a tail-recursive version using an accumulator parameter or continuation-passing style (CPS). However, not all recursive functions can be trivially rewritten — functions that make multiple recursive calls (like tree traversal or Fibonacci) require techniques like CPS or explicit stack simulation. The practical value of tail recursion depends on whether the language performs tail-call optimization (TCO): Scheme, Haskell, Kotlin, and Scala do; Python, Java, and most JavaScript engines do not.

Standard Recursion vs Tail Recursion

python

1# Standard recursion — NOT tail recursive
2# The multiplication happens AFTER the recursive call returns
3def factorial(n):
4    if n <= 1:
5        return 1
6    return n * factorial(n - 1)  # Must multiply after call returns
7# Stack: factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ...
8
9# Tail recursive — the recursive call IS the last operation
10def factorial_tail(n, acc=1):
11    if n <= 1:
12        return acc
13    return factorial_tail(n - 1, n * acc)  # Nothing to do after call
14# Stack (with TCO): factorial_tail(5,1) → factorial_tail(4,5) → factorial_tail(3,20) → ...

In tail recursion, the recursive call is the very last thing the function does — no computation happens after it returns. This allows the compiler to reuse the current stack frame, eliminating stack growth.

Technique 1: Accumulator Parameter

For linear recursion (one recursive call), add an accumulator that carries the intermediate result:

python

1# Sum of list — standard recursion
2def sum_list(lst):
3    if not lst:
4        return 0
5    return lst[0] + sum_list(lst[1:])  # Addition after call
6
7# Tail recursive with accumulator
8def sum_list_tail(lst, acc=0):
9    if not lst:
10        return acc
11    return sum_list_tail(lst[1:], acc + lst[0])
12
13# Reverse a list
14def reverse_tail(lst, acc=None):
15    if acc is None:
16        acc = []
17    if not lst:
18        return acc
19    return reverse_tail(lst[1:], [lst[0]] + acc)

scala

1// Scala — compiler optimizes tail recursion with @tailrec
2import scala.annotation.tailrec
3
4@tailrec
5def factorial(n: Int, acc: Int = 1): Int = {
6  if (n <= 1) acc
7  else factorial(n - 1, n * acc)  // Compiler verifies this is tail recursive
8}

Technique 2: Continuation-Passing Style (CPS)

For tree recursion (multiple recursive calls), accumulators are not enough. CPS transforms the "what to do next" into an explicit function parameter:

python

1# Fibonacci — two recursive calls, NOT tail recursive
2def fib(n):
3    if n <= 1:
4        return n
5    return fib(n - 1) + fib(n - 2)
6
7# CPS version — tail recursive (but builds up continuations)
8def fib_cps(n, cont=lambda x: x):
9    if n <= 1:
10        return cont(n)
11    return fib_cps(n - 1, lambda a:
12        fib_cps(n - 2, lambda b:
13            cont(a + b)))
14
15print(fib_cps(10))  # 55

CPS makes the function tail-recursive, but the continuations consume heap memory instead of stack. The total memory is the same — it is just moved from stack to heap.

Technique 3: Explicit Stack (Iterative Simulation)

Any recursion can be converted to iteration with an explicit stack:

python

1# Tree traversal — not trivially tail-recursive
2class Node:
3    def __init__(self, val, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8# Recursive (standard)
9def inorder(node):
10    if node is None:
11        return []
12    return inorder(node.left) + [node.val] + inorder(node.right)
13
14# Iterative with explicit stack
15def inorder_iterative(root):
16    result = []
17    stack = []
18    current = root
19    while current or stack:
20        while current:
21            stack.append(current)
22            current = current.left
23        current = stack.pop()
24        result.append(current.val)
25        current = current.right
26    return result

Which Functions Are Trivially Tail-Recursive?

Pattern	Trivially tail-recursive?	Technique needed
Linear recursion (one call)	Yes	Accumulator
Linear with post-processing	Yes	Accumulator
Tree/multi-branch recursion	No	CPS or explicit stack
Mutual recursion (A calls B, B calls A)	Possible	Trampoline or CPS
Divide and conquer (merge sort)	No	CPS or iterative

Language Support for Tail-Call Optimization

scheme

1;; Scheme — guaranteed TCO by specification
2(define (factorial n acc)
3  (if (<= n 1)
4      acc
5      (factorial (- n 1) (* n acc))))
6
7(factorial 1000000 1)  ; Works — no stack overflow

kotlin

1// Kotlin — tailrec keyword ensures TCO
2tailrec fun factorial(n: Long, acc: Long = 1): Long {
3    if (n <= 1) return acc
4    return factorial(n - 1, n * acc)
5}
6
7factorial(100000)  // Works — compiled to a loop

python

1# Python — NO TCO, tail recursion still overflows
2def factorial_tail(n, acc=1):
3    if n <= 1:
4        return acc
5    return factorial_tail(n - 1, n * acc)
6
7factorial_tail(10000)  # RecursionError: maximum recursion depth exceeded

Language	TCO?	Notes
Scheme/Racket	Yes (required by spec)	All tail calls optimized
Haskell	Yes	Lazy evaluation complicates analysis
Scala	Yes (`@tailrec`)	Self-recursive calls only
Kotlin	Yes (`tailrec`)	Self-recursive calls only
Erlang/Elixir	Yes	Critical for process loops
JavaScript	Partial	Only Safari supports TCO (ES6 spec requires it)
Python	No	Guido explicitly rejected TCO
Java	No	JVM does not support tail calls
C/C++	Compiler-dependent	GCC/Clang optimize in `-O2`

Trampoline: TCO Without Language Support

python

1# Trampoline — manual TCO for languages without it
2def trampoline(fn, *args):
3    result = fn(*args)
4    while callable(result):
5        result = result()
6    return result
7
8def factorial_trampoline(n, acc=1):
9    if n <= 1:
10        return acc
11    return lambda: factorial_trampoline(n - 1, n * acc)
12
13print(trampoline(factorial_trampoline, 100000))  # Works in Python!

The trampoline replaces recursion with a loop that repeatedly calls returned functions, avoiding stack growth.

Common Pitfalls

Assuming tail recursion prevents all stack overflow: Tail recursion only helps if the language implements TCO. In Python and Java, tail-recursive functions still overflow the stack because these languages do not optimize tail calls.
CPS does not reduce memory usage: CPS moves memory consumption from the stack to the heap (closures). It prevents stack overflow but does not reduce total memory usage. For deeply recursive functions, iterative solutions with explicit stacks are more memory-efficient.
Forgetting that @tailrec (Scala) and tailrec (Kotlin) only work for self-recursion: These annotations optimize direct self-calls only. Mutual recursion (A calls B, B calls A) is not optimized. Use trampolines for mutual tail recursion.
Making a function "look" tail-recursive without actually being tail-recursive: return 1 + f(n-1) is NOT tail-recursive because addition happens after the recursive call. The call must be the absolute last operation — no wrapping computation.
Premature optimization with tail recursion: In many languages, a simple iterative loop is clearer and equally performant. Tail recursion is most valuable in functional languages where loops do not exist. In Python or Java, prefer iteration for performance-critical code.

Summary

Any recursive function can be rewritten as tail-recursive using accumulators (linear) or CPS (tree)
Tail recursion only eliminates stack growth if the language performs tail-call optimization (TCO)
Languages with guaranteed TCO: Scheme, Haskell, Scala (@tailrec), Kotlin (tailrec), Erlang
Languages without TCO: Python, Java, most JavaScript engines
Use trampolines to achieve TCO-like behavior in languages without native support
For tree recursion, explicit stack iteration is often simpler and more efficient than CPS