return statement returns None instead of value

Question

I have run into a weird problem. This code returns None instead of True, even though it goes in to the correct branch and evaluates to True:

edges = { (1, 'a') : [2, 3],
          (2, 'a') : [2],
          (3, 'b') : [4, 3],
          (4, 'c') : [5] }
accepting = [2, 5] 
loc = []
def nfsmsim(string, current, edges, accepting): 

    if string != "":
        if ((current, string[0]) in edges.keys()):
            global loc 
            loc = edges[(current, string[0])]
            print "edge found:",loc

    if (string == ""):
        print "string is over",current,accepting
        print type(current), type(accepting)
        if current in accepting : 
            print "1"
            return True
        else: 
            print "2"
            return 2
    # fill in your code here 
    elif (current, string[0]) in edges.keys():
        global loc
        string = string[1:]
        nfsmsim(string, loc[0], edges, accepting)
    elif len(loc)>1:
        global loc
        nfsmsim(string, loc[1], edges, accepting)


# This problem includes some test cases to help you tell if you are on
# the right track. You may want to make your own additional tests as well.
print nfsmsim("abc", 1, edges, accepting)

The output of this is :

 string is over 5 [2, 5]
<type 'int'> <type 'list'>
1
None (<< instead of True)

Answer 1

This is a recursive function. When you reach the terminal case (string == ""), you return 1 or 2. That gets returned to the calling function -- the previous call of nfsmsim. But that call of of nfsmsim doesn't return anything! You need to get the value from the terminal call of nfsmsim and pass it on by returning it again.

In other words, you need a return statement in each of these two branches of your if statement:

elif (current, string[0]) in edges.keys():
    global loc
    string = string[1:]
    nfsmsim(string, loc[0], edges, accepting)
elif len(loc)>1:
    global loc
    nfsmsim(string, loc[1], edges, accepting)

Answer 2

Not using a return command when the function ends is the same as using return None.

As the function is recursive and you are using its result, you must return the value of every of its call also inside its body:

elif (current, string[0]) in edges.keys():
    global loc
    string = string[1:]
    return nfsmsim(string, loc[0], edges, accepting)
elif len(loc)>1:
    global loc
    return nfsmsim(string, loc[1], edges, accepting)

You should forget about using the global loc. Just pass it via the argument. It is a reference anyway:

edges = { (1, 'a') : [2, 3],
          (2, 'a') : [2],
          (3, 'b') : [4, 3],
          (4, 'c') : [5] }
accepting = [2, 5] 
loc = []
def nfsmsim(string, current, edges, accepting, loc): 

    if string != "":
        if ((current, string[0]) in edges.keys()):
            loc = edges[(current, string[0])]
            print "edge found:",loc

    if (string == ""):
        print "string is over",current,accepting
        print type(current), type(accepting)
        if current in accepting : 
            print "1"
            return True
        else: 
            print "2"
            return 2
    # fill in your code here 
    elif (current, string[0]) in edges.keys():
        string = string[1:]
        return nfsmsim(string, loc[0], edges, accepting, loc)
    elif len(loc)>1:
        return nfsmsim(string, loc[1], edges, accepting, loc)


# This problem includes some test cases to help you tell if you are on
# the right track. You may want to make your own additional tests as well.
print nfsmsim("abc", 1, edges, accepting, loc)

It prints the following on my console:

c:\tmp\___python\fixxxer\so10274792>python a.py
edge found: [2, 3]
edge found: [4, 3]
edge found: [5]
string is over 5 [2, 5]
<type 'int'> <type 'list'>
1
True