[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

I passed a fizzbuzz test but failed at recursion.

bsagert

3/10/2010 3:55:00 PM

Look at this recursive fizzbuzz function from
http://www.codinghorror.com/blog/2007/02/why-cant-programmers-pr...

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'
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".

My logic is wrong, but I don't know why.
3 Answers

Chris Hulan

3/10/2010 4:24:00 PM

0

On Mar 10, 10:55 am, Bill <bsag...@gmail.com> wrote:
> Look at this recursive fizzbuzz function fromhttp://www.codinghorror.com/blog/2007/02/why-cant-programme......
>
> 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'
>         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".
>
> My logic is wrong, but I don't know why.

There's only one print, it prints the string returned by fizzbuzz(100)
The string is constructed via recursion
ie:
fizzbuzz(6)
fizzbuzz(5)
fizzbuzz(4)
fizzbuzz(3)
fizzbuzz(2)
fizzbuzz(1)
fizzbuzz(0)
''+'1 \n'
'1 \n'+'2 \n'
'1 \n2 \n'+'fizz \n'
'1 \n2 \n fizz \n'+'4 \n'
'1 \n2 \n fizz \n4 \n'+'buzz \n'
'1 \n2 \n fizz \n4 \nbuzz \n'+'fizz \n'

print '1 \n2 \n fizz \n4 \nbuzz \nfizz \n'

clear as mud ;)

Terry Reedy

3/10/2010 5:53:00 PM

0

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-pr...
>
> 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

Michael Rudolf

3/14/2010 11:26:00 AM

0

Am 10.03.2010 16:55, schrieb Bill:
> 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'
> else : return fizzbuzz(num-1) + ('%d \n' % num)
> return ''
> print fizzbuzz(100)

While I do understand that this is not a Perl group, and this probably
won't help the OP, I just could not resist:

for i in range(1,101):print('','fizz')[not i%3]+('','buzz')[not i%5]or i

> 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".

No, the function creates the string from right to left.
See:
fizzbuzz(100) = fizzbuzz(99) + "buzz \n"
= fizzbuzz(98) + "fizz \n" + "buzz \n"

....

= fizzbuzz(1) + "2 \n" + "fizz \n" + "4 \n" + "buzz\n " + "fizz \n" +
..... + "97 \n" + "98 \n" + "fizz \n" + "buzz \n"

= fizzbuzz(0) + "1 \n" + "2 \n" + "fizz \n" + "4 \n" + "buzz\n " + "fizz
\n" + .... + "97 \n" + "98 \n" + "fizz \n" + "buzz \n"

= " " + "1 \n" + "2 \n" + "fizz \n" + "4 \n" + "buzz\n " + "fizz \n" +
..... + "97 \n" + "98 \n" + "fizz \n" + "buzz \n"

Regards,
Michael