python recursive function

[Tom_chicollegeboy]

here is what I have to do:

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.

For example, suppose that you start with 250 bears. Then you could
make these moves:

Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.


Usage:
False


As you see my program must use recursion.

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

 

[Gary Herron]

here is what I have to do:

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

This sounds very much like a homework assignment, and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.

Gary Herron

 

[Bruno Desthuilliers]

Tom_chicollegeboy a écrit :
(snip)

As you see my program must use recursion.

It's conceptually easier to express using recursions - but every
recursion-based algorithm can be rewritten to use iteration (and
vice-versa).

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)

You want:
return bears(n - 42)

 

[Bruno Desthuilliers]

Gary Herron a écrit :

This sounds very much like a homework assignment,
Indeed.

and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.

Garry, you should have read the whole post before answering. The OP's
attempt at solving the problem was below, along with the question.

(snip)

 

[cokofreedom]

This sounds very much like a homework assignment, and so should probably
not be answered here. (Neither should it have been asked here.) If,
in your attempt to write this program, you have some questions about
Python, then I encourage to ask those questions here.

Gary Herron

Note that for ;
if one!=0 and two!=0:

you can use
if one and two:

which is my pythonic.

Also in your example with 52, shouldn't it divide by even first?
Obviously this must not happen, thus maybe you should run a check that
when you are returning a new value it does not go below 42? Frankly
this looks like a terrible way to use recursion.

 

[Duncan Booth]

You want:
return bears(n - 42)

Actually, no he doesn't. He needs to explore all options when the first
attempt fails. But I'm not going to write his homework for him.

 

[Chris]

here is what I have to do:

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.

For example, suppose that you start with 250 bears. Then you could
make these moves:

Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.

Usage:


False

As you see my program must use recursion.

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

Stylistically I prefer 'if not n % 5', looks neater.
As for your assignment, the hardest task will be creating an effective
method of ensuring you recurse through all possibilities.

ie. do you brute force on every step, or when getting to step do you
fork your possibilities.
That is more a design question rather than a python one though.

 

[cokofreedom]

Stylistically I prefer 'if not n % 5', looks neater.

As for your assignment, the hardest task will be creating an effective
method of ensuring you recurse through all possibilities.

I was chatting to a friend about the 'if not n % 5' and while I am
happy to use it saying that when 5 % 5 is False because it returns
0...for this case just feels wrong to me.

I understand the reason to keep it this way...but still...having to
use not all the time is just annoying.

 

[HYRY]

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

try this:

def bears (n):
if n==42:
return True
if n%5==0:
if bears(n-42):
return True
if n%2==0:
if bears(n/2):
return True
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
if bears(n-(one*two)):
return True
return False

print bears(42)
print bears(250)
print bears(50)
print bears(84)
print bears(41)

 

[Bruno Desthuilliers]

Duncan Booth a écrit :

Actually, no he doesn't. He needs to explore all options when the first
attempt fails.

Possibly - I didn't bother checking the algorithm correctness, just
pointed out an obvious newbie programming error.

But I'm not going to write his homework for him.

Nor do I.

 

[Nick Craig-Wood]

def bears (n):
if n==42:
return True
if n%5==0:
if bears(n-42):
return True
if n%2==0:
if bears(n/2):
return True
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
if bears(n-(one*two)):
return True
return False

Almost but you missed a case...
.... try:
.... print i, bears(i)
.... except RuntimeError, e:
.... print i, e
....
0 0 maximum recursion depth exceeded
1 False
2 False
3 False
4 False
5 False
6 False
7 False
8 False
9 False
10 10 maximum recursion depth exceeded
11 False
12 12 maximum recursion depth exceeded
113 False
14 False
15 15 maximum recursion depth exceeded
16 16 maximum recursion depth exceeded
17 False
[snip]
89 False
90 90 maximum recursion depth exceeded
91 False
92 False
93 93 maximum recursion depth exceeded
94 False
95 False
96 96 maximum recursion depth exceeded
97 False
98 False
99 99 maximum recursion depth exceeded

 

[Fidtz]

here is what I have to do:

This question involves a game with teddy bears. The game starts when I
give you some bears. You then start giving me back some bears, but you
must follow these rules (where n is the number of bears that you
have):

If n is even, then you may give back exactly n/2 bears. (Hint: To test
whether n is even, use the expression ((n % 2) == 0).)
If n is divisible by 3 or 4, then you may multiply the last two digits
of n and give back this many bears. (By the way, the last digit of n
is n%10, and the next-to-last digit is (n%100)/10; this rule may not
be used if either of the last two digits is 0.)

If n is divisible by 5, then you may give back exactly 42 bears.
The goal of the game for you is to end up with EXACTLY 42 bears.

For example, suppose that you start with 250 bears. Then you could
make these moves:

Start with 250 bears.
Since 250 is divisible by 5, you may return 42 of the bears, leaving
you with 208 bears.
Since 208 is even, you may return half of the bears, leaving you with
104 bears.
Since 104 is even, you may return half of the bears, leaving you with
52 bears.
Since 52 is divisible by 4, you may multiply the last two digits
(resulting in 10) and return these 10 bears. This leaves you with 42
bears.
You have reached the goal!
Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.

Usage:


False

As you see my program must use recursion.

I came up with this idea but I am not sure if its right or are there
any minor errors that I can easily fix:

def bears (n):
if n==42:
return True
if n%5==0:
bears(n-42)
if n%2==0:
bears(n/2)
if n%3==0 or n%4==0:
one = (n%10)
two = ((n%100)/10)
if one!=0 and two!=0:
bears(n-(one*two))
return False

If a game hits 42 it should return True, otherwise False. If program
never hits 42 and return True, then it returns False. I figured out
base case, but I still get False when I enter bears(250). Any help
would be very appreciated!

May != Must and Could != Should

 

[Reedick, Andrew]

-----Original Message-----
From: [email protected] [mailtoython-
[email protected]] On Behalf Of Tom_chicollegeboy
Sent: Friday, January 11, 2008 3:30 AM
To: (e-mail address removed)
Subject: python recursive function

Now, you are to write a program that, if I give you n bears, returns
true if it is at all possible for you to win the game. Your program
must use recursion to check all possible ways in which you can apply
the rules.

if n==42:
return True

return False

You have to check for all possible paths. Returning True/False is
futile since the recursive chains will be returning a mix of true and
false. Use a global variable to indicate if a solution is found. (Or
pass the flag in using a list, since lists are passed by reference (if n
== 42: found_it[0] = True; return.)

There's also another teaching exercise in here. Do you follow the
literal directions ('check all possible ways') and generate all possible
paths? Or do you 'interpret' that to mean try all possible paths until
you find a solution? (i.e. do you short circuit the recursion once you
have a solution?)

One of the most difficult things about programming is conveying the
requirements from Human A to Human Programmer B. This is especially
difficult since business people and techies speak different languages
and, more importantly, think differently (different assumptions,
different paradigms, different levels of hand-waving away of details,
etc..) And don't get me started about the people in marketing...



*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA623

 

[Steven D'Aprano]

Almost but you missed a case...

Why are you people doing the OP's homework for him? And then DEBUGGING it
as well? Haven't you got something better to do than to help create a new
generation of incompetent, under-educated programmers?