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, Oct 17 '13 at 23:49
That depends. Is that your actual code? Because when I try it, I get an `IndentationError` before it can even run anything… — abarnert, Oct 18 '13 at 00:47
Yea, that is my code. I tried editing it again. It's working on my end, insofar as there are no errors. — mr.plow, Oct 18 '13 at 01:01
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](http://effbot.org/zone/default-values.htm) — wwii, Oct 18 '13 at 01:14
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, Oct 18 '13 at 01:25

score -2 · Answer 1 · edited May 23 '17 at 10:25

-2

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?

edited May 23 '17 at 10:25

Community

1
1

answered Oct 17 '13 at 23:39

joeButler

1,643
1
20
41

So I would need to call it from outside of any loops? – mr.plow Oct 17 '13 at 23:46
Calling it from within a loop is irrelevant. If that loop is inside the function body, it's recursive. If it's outside the function body, it's not. – abarnert Oct 17 '13 at 23:50
@mr.plow: I'm saying that the whole thing about "outside of any loops" is a red herring. If you call the function from inside the function body, it's recursive. If you don't, it's not recursive. And, as I explained above, if you don't fix the indentation, we can't actually tell whether your function is recursive or not. – abarnert Oct 18 '13 at 00:35
To whoever downvoted - my response was valid until the indentation was corrected. – joeButler Oct 18 '13 at 14:07

Python recursive function not descending

1 Answers1