# Tail-call Optimization¶

```from macropy.experimental.tco import macros, tco

@tco
def fact(n, acc=1):
if n == 0:
return acc
else:
return fact(n-1, n * acc)

print(fact(10000))  # doesn't stack overflow
# 28462596809170545189064132121198688901...
```

Tail-call Optimization is a technique which will optimize away the stack usage of functions calls which are in a tail position. Intuitively, if a function A calls another function B, but does not do any computation after B returns (i.e. A returns immediately when B returns), we don’t need to keep around the stack frame for A, which is normally used to store where to resume the computation after B returns. By optimizing this, we can prevent really deep tail-recursive functions (like the factorial example above) from overflowing the stack.

The `@tco` decorator macro doesn’t just work with tail-recursive functions, but also with any generic tail-calls (of either a function or a method) via trampolining, such this mutually recursive example:

```from macropy.experimental.tco import macros, tco

class Example(object):

@tco
def odd(n):
if n < 0:
return odd(-n)
elif n == 0:
return False
else:
return even(n - 1)

@tco
def even(n):
if n == 0:
return True
else:
return odd(n-1)

print(Example().even(100000))  # No stack overflow
# True
```

Note that both `odd` and `even` were both decorated with `@tco`. All functions which would ordinarily use too many stack frames must be decorated.

## Trampolining¶

How is tail recursion implemented? The idea is that if a function `f` would return the result of a recursive call to some function `g`, it could instead return `g`, along with whatever arguments it would have passed to `g`. Then instead of running `f` directly, we run `trampoline(f)`, which will call `f`, call the result of `f`, call the result of that `f`, etc. until finally some call returns an actual value.

A transformed (and simplified) version of the tail-call optimized factorial would look like this

```def trampoline_decorator(func):
def trampolined(*args):
if not in_trampoline():
return trampoline(func, args)
return func(*args)
return trampolined

def trampoline(func, args):
_enter_trampoline()
while True:
result = func(*args)
with patterns:
if ('macropy-tco-call', func, args) << result:
pass
else:
if ignoring:
_exit_trampoline()
return None
else:
_exit_trampoline()
return result

@trampoline_decorator
def fact(n, acc):
if n == 0:
return 1
else:
return ('macropy-tco-call', fact, [n-1, n * acc])
```