# 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])
```