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:

>>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!

[Gary Herron]

Tom_chicollegeb oy 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:

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:

>>>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!

[Bruno Desthuilliers]

Tom_chicollegeb oy 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

[Bruno Desthuilliers]

Gary Herron a écrit :

Tom_chicollegeb oy 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)

[cokofreedom]

On Jan 11, 9:46 am, Gary Herron <gher...@island training.comwro te:

Tom_chicollegeb oy 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:

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:

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

[Duncan Booth]

Bruno Desthuilliers <br************ ********@wtf.we bsiteburo.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.

[Chris]

On Jan 11, 10:30 am, Tom_chicollegeb oy <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:

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:

>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
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 :

Bruno Desthuilliers <br************ ********@wtf.we bsiteburo.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.