# Tail-recursive even/odd

Tail calls are a way to save on call stack space. If a function call happens as a last thing a function performs, then it is possible for a language implementation to optimize the call by getting rid of all temporary values on the stack before the call is made.

Consider this implementation of `even`

and `odd`

functions in Python:

```
def even(x):
if x == 0:
return True
return odd(x-1)
def odd(x):
if x == 0:
return false
return even(x-1)
```

Here, the recursive calls are in the "tail" position, and thus in theory it is possible to just discard the caller's stack and proceed with evaluating the callee without making a regular function call. In Python there are no tail calls, but it's not hard to implement in a virtual machine.

So, this is what I did in my virtual machine. Here's the same example written in the VM assembly:

```
;; Pick a reasonably big number
;; to demonstrate that we don't
;; use stack much
(const val 1000000)
(const one 1)
(const zero 0)
(sr 3)
(setjump r0 even)
(mov r1 val)
(call r0 1)
(aeq r0 one)
(retnil)
;; Even implementation
(label even)
(sr 3)
(jeq r0 zero even-end)
(setjump r1 odd)
(sub r2 r0 one)
(tailcall r1 1)
(label even-end)
(ret one)
;; Odd implementation
(label odd)
(sr 3)
(jeq r0 zero odd-end)
(setjump r1 even)
(sub r2 r0 one)
(tailcall r1 1)
(label odd-end)
(ret zero)
```

In places where we want to make a tail call, instead of using `call`

, you need to use `tailcall`

. But otherwise the way you write such calls would be the same.