Skip to content

Instantly share code, notes, and snippets.

@machinaut
Created December 20, 2011 09:00
Show Gist options
  • Save machinaut/1500869 to your computer and use it in GitHub Desktop.
Save machinaut/1500869 to your computer and use it in GitHub Desktop.
Solving the mystery of python recursion + continuations
#!/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.
@nitely
Copy link

nitely commented Mar 3, 2017

@machinaut got the job? :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment