445,908 Members | 2,055 Online Need help? Post your question and get tips & solutions from a community of 445,908 IT Pros & Developers. It's quick & easy.

# python recursive function

 P: n/a 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! Jan 11 '08 #1
12 Replies

 P: n/a 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

 P: n/a 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 Igive you some bears. You then start giving me back some bears, but youmust follow these rules (where n is the number of bears that youhave): 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

 P: n/a On Jan 11, 9:46 am, Gary Herron >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

 P: n/a Bruno Desthuilliers 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

 P: n/a On Jan 11, 10:30 am, Tom_chicollegeboy 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. Jan 11 '08 #7

 P: n/a 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

 P: n/a 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

 P: n/a Duncan Booth a écrit : Bruno Desthuilliers 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

 P: n/a HYRY >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

 P: n/a On 11 Jan, 08:30, Tom_chicollegeboy 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

 P: n/a On Fri, 11 Jan 2008 06:30:04 -0600, Nick Craig-Wood wrote: HYRY 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. 