Python recursive function not descending

Question

I'm having trouble with a recursive function I'm trying to write. It looks like the function just isn't descending. I'm not getting any errors or anything, so I don't really get what's going on. The only output I get out of it are some empty lists. Essentially I'm trying to keep track of all the paths that my program can take through some given input, and return a list holding all those paths. I'm really, really, really new to python, so there's a lot I don't know. I'm also really new to stackoverflow, so forgive the formatting errors. Thanks in advance!

def Process ( fst, input, start_state, current_path=[], input_index=0 ):
    current_line = input.replace('"', '')
    current_state = start_state
    probability = 1
    result = []
    state_paths = []
    this_path = current_path
    paths_found = []
    epsilon_paths_found = []
    temp_list = []
    index = input_index


    if not index < len( current_line ):
        return this_path

    item = current_line[index]

    if not item.isspace():
        for edge in fst.transitions[current_state]:
            next_state = current_state
            if item == edge.input:
                paths_found.append( edge )
                index += 1
            for x in paths_found:
                temp_list = this_path
                temp_list.append( x )
                temp_entry = Process( fst, input, x.target_state, temp_list, index )
                state_paths.append( temp_entry )

            #epsilon returns a list
            epsilon = EpsilonStates( fst.transitions[current_state] )

            if epsilon:
                index -= 1
                for i in epsilon: 
                    epsilon_paths_found.append( i )
                 for y in epsilon_paths_found:
                    temp_list = this_path
                    temp_list.append( y )
                    state_paths.append( Process( fst, input, y.target_state, temp_list, index ) )
    return state_paths

Can you fix the indentation? It's not clear here where the definition of Process ends and the top-level module code begins—and that's crucial to answering your question. — abarnert
That depends. Is that your actual code? Because when I try it, I get an IndentationError before it can even run anything… — abarnert
Yea, that is my code. I tried editing it again. It's working on my end, insofar as there are no errors. — mr.plow
Print statements are a good way to find out what is happening when your code is executing - but they can sometimes be hard to interpret for recursive procedures. Maybe just start with print locals() as the first line of Process. I see that you are using a mutable data type (list) as a default argument - that can definitely cause problems. Try a google search for "python mutable default arguments". http://effbot.org/zone/default-values.htm — wwii
No, that cannot be your code. Copy it and paste it and try to run it, and you will see that it doesn't even parse. I can immediately spot one problem—the return at the end is dedented to the same level as the def. But I have no idea if that's the only place that your post is different from your real code. It's up to you to post something that we can read, run, and debug, not for us to try to guess what your real code looks like. — abarnert

joeButler joeButler · Accepted Answer · 2013-10-17T23:39:10

For recursion to happen, your process function would need to call itself. Normally with a sub-set of the initial function arguments.

In your code, you are calling the Process function from a for loop. So this would not be recursive.

This thread has an example of a recursive function, and an example of why the arguments are reduced on subsequent calls:

How can I build a recursive function in python?

Python recursive function not descending

1 Answers