How recursive functions work inside a 'for loop'

Question

I'm fairly new in 'recursive functions'. So, I'm trying to wrap my head around why we use recursive functions and how recursive functions work and I think I've a fairly good understanding about it.

Two days ago, I was trying to solve the shortest path problem. I've a following graph(it's in python):

 graph = {'a': ['b', 'c'],
             'b': ['c', 'd'],
             'c': ['d'],
             'd': ['c'],
             'e': ['f'],
             'f': ['c']}

I'm just trying to find a path, not the shortest path.So, here is the code:

def find_path(graph,start,end,path=[]):
    path = path + [start]
    #Just a Test
    print(path)

    if start == end:
        return path

    if start not in graph:
        return None

    for node in graph[start]:
        if node not in path:
            new_path = find_path(graph,node,end,path)
        if new_path:
            #Just a test
            print(path)
            return new_path

print(find_path({'a':['b','c'],'b':['c','d'],'c':['d'],'d':['c'],'e':
['f'],'f':['c']},'a','d'))

My starting vertex is 'a' and the ending vertex is 'd'.

In the fourth line I just printed the 'path' to see where the path goes.

On line 17th I also printed the 'path', again just to test. And here is the result:

['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'c']
['a', 'b']
['a']
['a', 'b', 'c', 'd']

The first four lines of the result is the result of 'print(path)' on line 4 of the code. But, line 5th, 6th and 7th is the result of 'print(path)' on line 17th of the code.

My question is why the list of the path is decreasing by one vertex each time?

I've been trying to find it's solution for 2 days. I've went to forums, read the documentation about recursion and watched videos. But, no luck.

I would be greatful if somebody can answer.

Answer 1

This is because recursion yields results from "innermost" to "outermost" calls. That is the first line 17 print statement occurs from the deepest recursion level where the path has the most nodes. After that level returned the next level "upwards" is printed (one node less in the path). Note that your print function comes after the recursive call to find_path.

You can visualize it as follows:

find_path(..., path=['a'])  # Recursion level 1.
|
|   find_path(..., path=['a', 'b'])  # Recursion level 2.
|   |
|   |   find_path(..., path=['a', 'b', 'c'])  # Recursion level 3.
|   |   print(path)  # Prints ['a', 'b', 'c'].
|   |   return  # Return from level 3.
|   |
|   print(path)  # Prints ['a', 'b'].
|   return  # Return from level 2.
|
print(path)  # Prints ['a'].
return  # Return from level 1.

If you want the single (sub-)paths to be printed in "increasing" order then you can simply place the print function before the recursive call to find_path.

It's the new_path variable which holds the recursively found path while path just holds the path to the current node.

By the way the if new_path: clause might fail if the previous if branch has not been entered yet because then new_path is undefined.

Answer 2

First I am just going to give an explanation of what backtracking means. I also posted this answer here.

Recursion means to call the function from within that same function. Now what happens is that when the function encounters a call to itself.. imagine that a new page opens up and control is transferred from the old page onto this new page to the start of the function, when the function encounters the call again in this new page, another page opens up beside it and in this way new pages keep popping up beside the old page. Do note that all the local variables are only in scope with their respective pages. That is if you want to access the value in the previous page you either pass it to the function in parameters or make the variable global.

The only way to go back is using return statement. When the function encounters it the control goes from the new page back to the old page on the same line from where it was called and starts executing whatever is below that line. This is where backtracking starts. In order to avoid issues like feeding data again when its filled up you usually need to put a return statement after every call to the function.

Now in your code,

def find_path(graph,start,end,path=[]):
    path = path + [start]
    #Just a Test
    print(path)

    if start == end:
        return path

    if start not in graph:
        return None

    for node in graph[start]:
        if node not in path:
            new_path = find_path(graph,node,end,path)  <---- when function returns it will start executing from here again.
        if new_path:
            #Just a test
            print(path)
            return new_path

And note that your path variable is not a global variable. It's a local. This means everytime you call its resetted. To avoid this you are passing the path value again in the function parameters (in the last).

So finally when the function returns after it has found d it returns to the previous state where the path variable has only a, b, c in it. that's what you print out.

Edit:- Just in case anybody objects, my explanation of recursion using pages is purely non-technichal, if you want to know how it really happens then you'll have to read about activation record and how it pushes all the state onto a stack

Answer 3

1) The find_path method is first called with a as the start node which sets the path as ['a'] and calls the find_path method with b as the start node before printing path on line 17.

2) The call to find_path method with b as the start node sets the path as ['a','b'] and calls the find_path method with c as the start node before printing path on line 17.

3) The call to find_path method with c as the start node sets the path as ['a','b','c'] and calls the find_path method with d as the start node before printing path on line 17.

4) The call to find_path method with d as the start node sets the path as ['a','b','c','d'] prints it on line 4 and returns.

5) Now it returns on line 14 in the execution of method find_path with c as the start node (which had set the path as ['a','b','c'] as mentioned in point 3) and prints path on line 17 (which is line 5th of your result) and returns.

6) This returns on line 14 in the execution of method find_path with b as the start node (which had set the path as ['a','b'] as mentioned in point 2) and prints path on line 17 (which is line 6th of your result) and returns.

7) This returns on line 14 in the execution of method find_path with a as the start node (which had set the path as ['a'] as mentioned in point 1) and prints path on line 17 (which is line 6th of your result) and returns.

You can imagine it as LIFO (Last In First Out)