Solving the mystery of python recursion + continuations

paren.py

#!/usr/bin/env python
#paren.py - solve paren problem

# We want all combinations of N left and right parens that are correct
# (so every right comes after it's corresponding left)

# Can it be done recursively using continuations?
# I wondered this sitting in the hotel room the night before my google interview.
# And I couldnt sleep, so went about trying to figure out more.

# I *thought* the yield statement was a continuation. So basically if you called
# the function again it would continue where it left off.  But how would this deal
# with recursion?

# My basic first thoughts at a solution to the problem were this:

# n is the number of lefts and rights we're going to use
# l is the number of lefts so far
# r is the number of rights so far
# i is the input string (what we have so far)
def par(n,l,r,i):
  if l == n == r: # base case: we're done here
    yield i
  if l < n: # room for one more left
    for p in par(n,l+1,r,i+"("):
      yield p
  if r < l: # room for one more right
    for p in par(n,l,r+1,i+")"):
      yield p
def parcombo(n):
  return par(n,0,0,"")

# This is where it got weird, I didn't fully understand what it was going to do.
# According to my yield == continuations thought, it would basically keep reentering
# itself.  But wait, if you're recursing, you get new stacks every time you call, but
# if you're continuing, you get the same stack every time you call.  This obviously
# contradicts itself.  So how does it actually work?

# Turns out the yield statement isnt a continuation at all, it actually transforms the
# function call into a generator.

# GREAT explaination here on stackoverflow.com:
# http://stackoverflow.com/questions/231767/the-python-yield-keyword-explained

# tl;dr the yield statement actually makes it return a generator

# so just running that "dummy" code i couldn't make heads or tails of...
# ...actually worked!
for i in range(11):
  count = 0
  for p in parcombo(i):
    count += 1
    #print p #uncomment to see ALL THE PARENS
  print count

# It worked the way I wanted it to, because yield did not work the way I thought it did.

# Also: A neat postscript, Russ Cox is one of my personal heros.  Among many other things
# I find awesome (Plan 9/Go/6.828) he worked on OEIS: Online Encyclopedia of Integer Sequences

# So after solving this I entered the integer sequence of the number of correct combinations,
# to see what I could possibly correlate it to.

# Here it is, turns out it has a LOT of combinatorial interpretations
# https://oeis.org/A000108
# Cool! Turns out these are called Catalan numbers, and they have a closed form of:
# C(n) = binomial(2n,n)/n+1 = (2n)!/(n!(n++1)!)
# And they have their own wikipedia page:
# http://en.wikipedia.org/wiki/Catalan_number

# Alright, time to get some sleep before the google interview.

@machinaut got the job? :)