I passed a fizzbuzz test but failed at recursion.

Terry Reedy tjreedy at udel.edu
Wed Mar 10 12:52:47 EST 2010


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




More information about the Python-list mailing list