[Tutor] Recursion always returns None

[Hugo Arts]

On Tue, Aug 28, 2012 at 1:23 PM, Dharmit Shah <shahdharmit at gmail.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20120828/7851c045/attachment.html>