Caleb Madrigal

Programming, Hacking, Math, and Art


Recursion with asyncio

Recursion is awesome, but has the downside of growing the stack, which can limit its usefulness. Some languages like Scheme, however, have Tail-call optimization, which lets programmers write Tail-recursive functions that don't grow the call stack. Python does not have Tail-call optimization (TCO), but with asyncio, we can have something like Tail-call optimization. Basically, this method uses the asyncio event loop like a trampoline function.

Example: download
import asyncio

# Tail-recursive factorial using asyncio event loop as a trampoline to
# keep the stack from growing.
def factorial(n, callback, acc=1):
    if n == 0:
        asyncio.async(factorial(n-1, callback, acc*n)) # async -> ensure_future in Python 3.4.4

def done_callback(result):
    print("Result: {}".format(result))
    loop = asyncio.get_event_loop()

loop = asyncio.get_event_loop()
asyncio.async(factorial(50000, done_callback))
loop.run_forever() # Blocking call interrupted by loop.stop()

(Source on Github)

A few things to note:

  • This will NOT grow the call stack
  • This is about 2x slower than a loop-based iterative approach (at least for this factorial algorithm)
  • Notice the use of asyncio.async()
  • Notice that we are using a done callback - this is similar to Continuation-passing style.