Re: [Tutor] Recursion always returns None
On Tue, Aug 28, 2012 at 5:14 PM, Alan Gauld wrote: > On 28/08/12 17:34, Steve Willoughby wrote: >>> For some reason some beginners seem to find recursion a natural pattern. >> >> >> There is a certain "hey, you can do that? That's cool!" factor when you >> first discover recursion. > > > My point was that it seems to be a natural idea for many beginners, they > discover it without being told. They just assume it will work. > It comes up time and time again on this list from people who have > never heard of it but are using it. > > Whereas others who need to be explicitly taught about it find it totally > bizarre and mind bending. I've come to the conclusion that its a > right-brain, left-brain type of thing. For some it just seems logical, for > others perverse! > > Presumably John McCarthy was one of those who found it natural! :-) > > > -- > Alan G > Author of the Learn to Program web site > http://www.alan-g.me.uk/ > > ___ > Tutor maillist - Tutor@python.org > To unsubscribe or change subscription options: > http://mail.python.org/mailman/listinfo/tutor Interesting idea. I thought it was pretty cool when I studied it, and re-study recursion, but I seldom think of writing code with recursion. It scares me in an unnatural way. I think that best problems for recursion are ones with really deep data structures, and i fear they will run out of stack space. No evidence, just my take on using recursion as opposed to liking to read how small some recursive solutions are. -- Joel Goldstick ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28/08/12 17:34, Steve Willoughby wrote: For some reason some beginners seem to find recursion a natural pattern. There is a certain "hey, you can do that? That's cool!" factor when you first discover recursion. My point was that it seems to be a natural idea for many beginners, they discover it without being told. They just assume it will work. It comes up time and time again on this list from people who have never heard of it but are using it. Whereas others who need to be explicitly taught about it find it totally bizarre and mind bending. I've come to the conclusion that its a right-brain, left-brain type of thing. For some it just seems logical, for others perverse! Presumably John McCarthy was one of those who found it natural! :-) -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28-Aug-12 09:13, Alan Gauld wrote: On 28/08/12 16:51, Dharmit Shah wrote: @Dave Angel : Thank you for the loop idea. It didn't strike me at all. For some reason some beginners seem to find recursion a natural pattern. There is a certain "hey, you can do that? That's cool!" factor when you first discover recursion. When it naturally applies to a problem, it's still a powerful thing, but yes, it's often misapplied by beginners. -- Steve Willoughby / st...@alchemy.com "A ship in harbor is safe, but that is not what ships are built for." PGP Fingerprint 4615 3CCE 0F29 AE6C 8FF4 CA01 73FE 997A 765D 696C ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28-Aug-12 09:03, Mark Lawrence wrote: On 28/08/2012 16:51, Dharmit Shah wrote: @ Steve : Thank you. As suggested by Dave Angel, I am going to try the loop. And even before implementing it, I can feel that it's going to be more efficient than recursion. May I ask why you appear to be concerned with efficiency for a hangman game? Not the game per se, but if you're searching a file of thousands of words one at a time, randomly picking words and recursing if they're not what you intended, the hit--worst case--could be catastrophic. -- Steve Willoughby / st...@alchemy.com "A ship in harbor is safe, but that is not what ships are built for." PGP Fingerprint 4615 3CCE 0F29 AE6C 8FF4 CA01 73FE 997A 765D 696C ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28/08/12 16:51, Dharmit Shah wrote: @Dave Angel : Thank you for the loop idea. It didn't strike me at all. For some reason some beginners seem to find recursion a natural pattern. Many others, including quite experienced programmers find it a mind bending concept. But as a general rule, where you want to repeat an naction a number of times thing loops. If you know in advance how many times to repeat (eg all the items in a list) think 'for' loops, if you don't know how often (eg until some input condition is met) think 'while' loops. HTH, -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28/08/2012 16:51, Dharmit Shah wrote: @ Steve : Thank you. As suggested by Dave Angel, I am going to try the loop. And even before implementing it, I can feel that it's going to be more efficient than recursion. May I ask why you appear to be concerned with efficiency for a hangman game? -- Cheers. Mark Lawrence. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
Hello, @Hugo Arts : Thank you! That was awesome to read. Thanks for the len() suggestion. @ Steve : Thank you. As suggested by Dave Angel, I am going to try the loop. And even before implementing it, I can feel that it's going to be more efficient than recursion. @Dave Angel : Thank you for the loop idea. It didn't strike me at all. @All : Thanks a bunch for helping me out. :) Cheers, Dharmit On Tue, Aug 28, 2012 at 7:18 PM, Dave Angel wrote: > On 08/28/2012 07:23 AM, Dharmit Shah wrote: >> Hello, >> >> I am trying to do the following : >> >> 1) Ask user for the length of the word that he'd like to guess (for >> hangman game). >> 2) Pick a random word from /usr/share/dict/words (which I understand >> is not the best choice for hangman). >> 3) Call a function that would pick a random word to proceed further. >> >> Below is the code for the part I described above : >> >> [code] >> >> #!/bin/env python >> import random >> >> def pick_random(l, ln): # picks a random word from the list >> l of length ln >> global mystery >> word = random.choice(l) >> if word.__len__() != ln: >> pick_random(l, ln)# recursion >> else: >> print "Should return %s" % word # prints the chosen random >> word correctly >> return word # always >> return None, why? :( > > There's no return statement here, to cover the case where the if-clause > succeeded. > >> if __name__ == "__main__": >> ln = raw_input("How long word can you guess (number of alphabets) : ") >> ln = int(ln) >> l = [] >> with open("/usr/share/dict/words", "r") as f: >> for i in f.readlines(): >> i = i.split("\n")[0] >> if i.isalpha(): >> l.append(i) >> >> word = pick_random(l, ln) >> print word >> >> [/code] >> >> Sample output : >> >> $ python hangman.py >> How long word can you guess (number of alphabets) : 6 >> Should return inarch >> None >> $ >> >> The problem is that the last line "print word" always prints None. I >> know I am doing something wrong in the recursion part of the function >> "pick_random". Can someone please point what I am missing. Thank you! >> >> Cheers, >> Dharmit >> > > There are two things wrong, one of which has already been pointed out. > But the most fundamental thing that's wrong is that once you have called > the recursion, you don't return a value at all, simply falling off the > end of the function. Python returns a value of None when you omit the > return statement. > > So you should add a statement 'return word', which will eliminate the > None. But of course it'll be the wrong word. To fix that, you need to > assign the results of the call to pick_random() to the same local > variable, word. > > As others have pointed out, this is a poor choice for recursion. > Recursion can be more readable for some problems, when the problem > statement is naturally recursive. But even then, it can frequently lead > to stack overruns, and performance problems. But in this case a simple > loop would make much more sense. So unless the instructor is requiring > you to use recursion, please redo it as a loop. > > While we're at it, please use the len() function, rather than __len__() > method. And instead doing a split() method for eliminating the > linefeeds, what you really want to do is rstrip(). > > > > -- > > DaveA > -- Dharmit Shah www.about.me/dharmit ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 08/28/2012 07:23 AM, Dharmit Shah wrote: > Hello, > > I am trying to do the following : > > 1) Ask user for the length of the word that he'd like to guess (for > hangman game). > 2) Pick a random word from /usr/share/dict/words (which I understand > is not the best choice for hangman). > 3) Call a function that would pick a random word to proceed further. > > Below is the code for the part I described above : > > [code] > > #!/bin/env python > import random > > def pick_random(l, ln): # picks a random word from the list > l of length ln > global mystery > word = random.choice(l) > if word.__len__() != ln: > pick_random(l, ln)# recursion > else: > print "Should return %s" % word # prints the chosen random > word correctly > return word # always > return None, why? :( There's no return statement here, to cover the case where the if-clause succeeded. > if __name__ == "__main__": > ln = raw_input("How long word can you guess (number of alphabets) : ") > ln = int(ln) > l = [] > with open("/usr/share/dict/words", "r") as f: > for i in f.readlines(): > i = i.split("\n")[0] > if i.isalpha(): > l.append(i) > > word = pick_random(l, ln) > print word > > [/code] > > Sample output : > > $ python hangman.py > How long word can you guess (number of alphabets) : 6 > Should return inarch > None > $ > > The problem is that the last line "print word" always prints None. I > know I am doing something wrong in the recursion part of the function > "pick_random". Can someone please point what I am missing. Thank you! > > Cheers, > Dharmit > There are two things wrong, one of which has already been pointed out. But the most fundamental thing that's wrong is that once you have called the recursion, you don't return a value at all, simply falling off the end of the function. Python returns a value of None when you omit the return statement. So you should add a statement 'return word', which will eliminate the None. But of course it'll be the wrong word. To fix that, you need to assign the results of the call to pick_random() to the same local variable, word. As others have pointed out, this is a poor choice for recursion. Recursion can be more readable for some problems, when the problem statement is naturally recursive. But even then, it can frequently lead to stack overruns, and performance problems. But in this case a simple loop would make much more sense. So unless the instructor is requiring you to use recursion, please redo it as a loop. While we're at it, please use the len() function, rather than __len__() method. And instead doing a split() method for eliminating the linefeeds, what you really want to do is rstrip(). -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On 28-Aug-12 04:23, Dharmit Shah wrote: Hello, I am trying to do the following : 1) Ask user for the length of the word that he'd like to guess (for hangman game). 2) Pick a random word from /usr/share/dict/words (which I understand is not the best choice for hangman). 3) Call a function that would pick a random word to proceed further. Below is the code for the part I described above : I'm struggling to understand why you're using recursion here. It serves no evident purpose for what you're doing, and given a large dictionary of words, could seriously tank the performance of the application, quite possibly run it out of resources and crash it altogether. But since you're using recursion, note that when you make your recursive call, you're ignoring the return value from that call, so no returned value ever gets propagated out to the outer layers of recursion. If the outermost layer took the recursion (length of the chosen word is wrong), it calls itself and then never takes the branch including the return statement at all. ("return word" is never executed in that case). This causes the function to just 'fall off' the end which implicitly returns None. HTH [code] #!/bin/env python import random def pick_random(l, ln): # picks a random word from the list l of length ln global mystery word = random.choice(l) if word.__len__() != ln: pick_random(l, ln)# recursion else: print "Should return %s" % word # prints the chosen random word correctly return word # always return None, why? :( if __name__ == "__main__": ln = raw_input("How long word can you guess (number of alphabets) : ") ln = int(ln) l = [] with open("/usr/share/dict/words", "r") as f: for i in f.readlines(): i = i.split("\n")[0] if i.isalpha(): l.append(i) word = pick_random(l, ln) print word [/code] Sample output : $ python hangman.py How long word can you guess (number of alphabets) : 6 Should return inarch None $ The problem is that the last line "print word" always prints None. I know I am doing something wrong in the recursion part of the function "pick_random". Can someone please point what I am missing. Thank you! Cheers, Dharmit -- Steve Willoughby / st...@alchemy.com "A ship in harbor is safe, but that is not what ships are built for." PGP Fingerprint 4615 3CCE 0F29 AE6C 8FF4 CA01 73FE 997A 765D 696C ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Recursion always returns None
On Tue, Aug 28, 2012 at 1:23 PM, Dharmit Shah wrote: > Hello, > > I am trying to do the following : > > 1) Ask user for the length of the word that he'd like to guess (for > hangman game). > 2) Pick a random word from /usr/share/dict/words (which I understand > is not the best choice for hangman). > 3) Call a function that would pick a random word to proceed further. > > Below is the code for the part I described above : > > [code] > > #!/bin/env python > import random > > def pick_random(l, ln): # picks a random word from the list > l of length ln > global mystery > word = random.choice(l) > if word.__len__() != ln: > pick_random(l, ln)# recursion > else: > print "Should return %s" % word # prints the chosen random > word correctly > return word # always > return None, why? :( > > Okay, a good technique here is to just go over the program step by step, keeping track of the call stack. An interactive debugger is great for this, but it's good to be able to do it in your mind too. Let's say we call pick_random with ln=6, and the nice wordlist you have. Our call stack looks like so: main (not in a function) --> pick_random(l, ln) So, we pick a random word, then compare its length (by the way, you should use len(word), not word.__len__(); it's much nicer to read). Now we have two possible options, either the word is the right length or it isn't. The first case is pretty trivial (return the word, done). So let's consider the second case. This will happen a lot, the chances of picking a 6 character word right away are pretty low. Okay so what happens now? We call pick_word again, pretty simple. Call stack: main --> pick_random(l, ln) --> pick_random(l, ln) pick_random's on the call stack twice now, which is what recursion means. Now we could go on and say we don't find the right length word again, and again, and again, but it won't give us any more information here. We'd just keep stacking up the same function. So let's say the second call to pick_random found a right word, and returned it. Call stack: main --> pick_random(l, ln) We're back in the first pick_random function, right where we left off. And now we can see our error, right here: if word.__len__() != ln: pick_random(l, ln)# recursion What do we do with the return value of the recursive call? Well, nothing. It just disappears. And then we continue on, past the if statement, fall out of the function, and pick_random will return None. What we should have done, is this: if word.__len__() != ln: return pick_random(l, ln)# recursion In general, when you call a function you should always be mindful of whether it has a return value, and where its return value is going. And when you're doing recursion, it is very important to understand how the call stack works, and how you can stack multiple instances of the same function on top of each other. HTH, Hugo ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor