python recursion return None type

Question

I don't get it, how can i return a List instead of a None?

class foo():
    def recursion(aList):
        if isGoal(aList[-1]):
            return aList
        for item in anotherList:
            newList = list(aList)
            newList.append(item)
            recursion(newList)

    someList = [0]
    return recursion(someList)

Basically the code is to record all paths (start at 0). Whoever gets 100 first will be returned. isGoal() is to check if last item of the path is 100. And anotherList is a small list of random numbers (from 0 to 100).

Answer 1

return statement

This problem actually took me quite a while to grasp when I first started learning recursion.

One thing to keep in mind when dealing with Python functions/methods is that they always return a value no matter what. So say you forget to declare a return statement in the body of your function/method, Python takes care of it for you then and does return None at the end of it.

What this means is that if you screw up in the body of the function and misplace the return or omit it, instead of an expected return your print type(messed_up_function()) will print NoneType.

Recursion fix

Now with that in mind, when dealing with recursion, first make sure you have a base case besides the inductive case, I.e. to prevent an infinite recursive loop.

Next, make sure you're returning on both cases, so something like this:

def recur(val):
    """
    takes a string
    returns it back-to-front
    """
    assert type(val) == str
    # the base case
    if len(val) == 1:
        return val
    # the inductive case
    else:
        return val[-1] + recur(val[:-1]) # reverses a string char by char

So what this does is it always returns and is 100% infinite recursion proof because it has a valid base case and a decremented length at each inductive step.

Stack Viewer to debug recursive functions

In case we would run recur('big') with the added assert False at the start of the base case, we would have this stack structure:

From it we can see that at each recursive step, we have val, which is the only parameter of this function, getting smaller and smaller until it hits len(val) == 1 and then it reaches the final return, or in this case assert False. So this is just a handy way to debug your recursive functions/methods. In IDLE you can access such a view by calling Debug > Stack Viewer in the shell.