471,330 Members | 1,637 Online

# python recursive function

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:

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:
>>bears(42)
True
>>bears(250)
True
>>bears(50)
False
>>bears(84)
True
>>bears(41)
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!
Jan 11 '08 #1
12 2757 Tom_chicollegeboy wrote:
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

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:

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:

>>>bears(42)
True
>>>bears(250)
True
>>>bears(50)
False
>>>bears(84)
True
>>>bears(41)
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!
Jan 11 '08 #2
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)
if n%2==0:
bears(n/2)
idem
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))
idem
return False
Jan 11 '08 #3
Gary Herron a écrit :
Tom_chicollegeboy wrote:
>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,
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)
Jan 11 '08 #4
On Jan 11, 9:46 am, Gary Herron <gher...@islandtraining.comwrote:
Tom_chicollegeboy wrote:
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
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:
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:
>>bears(42)
True
>>bears(250)
True
>>bears(50)
False
>>bears(84)
True
>>bears(41)
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!
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.
Jan 11 '08 #5
Bruno Desthuilliers <br********************@wtf.websiteburo.oops.com >
wrote:
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.
Jan 11 '08 #6
On Jan 11, 10:30 am, Tom_chicollegeboy <tbab...@gmail.comwrote:
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:

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:
>bears(42)
True
>bears(250)
True
>bears(50)
False
>bears(84)
True
>bears(41)

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
That is more a design question rather than a python one though.
Jan 11 '08 #7
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.
Jan 11 '08 #8
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)
Jan 11 '08 #9
Duncan Booth a écrit :
Bruno Desthuilliers <br********************@wtf.websiteburo.oops.com >
wrote:
>You want:
return bears(n - 42)

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.
Jan 11 '08 #10
HYRY <ru*******@gmail.comwrote:
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...
>>for i in range(100):
.... 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

--
Nick Craig-Wood <ni**@craig-wood.com-- http://www.craig-wood.com/nick
Jan 11 '08 #11
On 11 Jan, 08:30, Tom_chicollegeboy <tbab...@gmail.comwrote:
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:

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:
>bears(42)
True
>bears(250)
True
>bears(50)
False
>bears(84)
True
>bears(41)

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
Jan 11 '08 #12
On Fri, 11 Jan 2008 06:30:04 -0600, Nick Craig-Wood wrote:
HYRY <ru*******@gmail.comwrote:
> def bears (n):
if n==42:
return True
....
> return False

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?

--
Steven
Jan 11 '08 #13

### This discussion thread is closed

Replies have been disabled for this discussion.