On 3/10/2010 10:55 AM, Bill wrote:
Look at this recursive fizzbuzz function from
http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html
def fizzbuzz(num):
if num:
if num % 15 is 0: return fizzbuzz(num-1) + 'fizzbuzz \n'
elif num % 5 is 0: return fizzbuzz(num-1) + 'buzz \n'
elif num % 3 is 0: return fizzbuzz(num-1) + 'fizz \n'
In all 3 branches, 'is' should be '=='. As written, this code depends on
the implementation treating 0 as a singleton, which CPython does as an
optimization, but which the language def does not require.
else : return fizzbuzz(num-1) + ('%d \n' % num)
return ''
print fizzbuzz(100)
This returns "1 2 fizz 4 ...etc... 97 98 fizz buzz" which is correct.
However, when I try to decipher the logic of the function I imagine
the solution reversed as "buzz fizz 98 97 ...etc... 4 fizz 2 1".
After all, the first num is 100 which decrements by one until a zero
stops the recursive loop.
My (faulty) reasoning is that fizzbuzz(100) would firstly print a
"fizz" and the last fizzbuzz(1) would finally print a "1".
If one reversed the string addition in each branch, it would.
As written, the 'word' for n is tacked on at the end.
My logic is wrong, but I don't know why.
Is this slightly revised version any clearer?
def fizzbuzz_rb(n):
if n:
previous = fizzbuzz_rb(n-1)
word = (not n % 15 and 'fizzbuzz \n' or
not n % 5 and 'buzz \n' or
not n % 3 and 'fizz \n' or
'%d \n' % n)
return previous + word
else:
return ''
or this equivalent tail-recursive version?
def fizzbuzz_rt(i,n,s):
if i <= n:
word = (not i % 15 and 'fizzbuzz \n' or
not i % 5 and 'buzz \n' or
not i % 3 and 'fizz \n' or
'%d \n' % i)
return fizzbuzz_rt(i+1, n, s+word)
else:
return s
or this equivalent iterative version?
def fizzbuzz_it(n):
s = ''
for i in range(1,n+1):
s += (not i % 15 and 'fizzbuzz \n' or
not i % 5 and 'buzz \n' or
not i % 3 and 'fizz \n' or
'%d \n' % i)
return s
print (fizzbuzz_rb(100) == fizzbuzz_rt(1,100,'') == fizzbuzz_it(100))
# prints True
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
