How do recursive functions work inside a for loop?

Question

I am new to 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 have a pretty good understanding about this.

Two days ago, I tried to solve the problem with the shortest path. I have the following graph (it is 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 simply typed “path” to see where the path goes.

On line 17, I also typed “path,” again just for verification. 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 are the result of "print (path)" in line 4 of the code. But line 5, 6 and 7 is the result of "print (path)" on line 17 of the code.

My question is why the list of paths decreases one vertex each time?

I tried to find a solution within 2 days. I went to the forums, read the recursion documentation, and watched the video. But no luck.

It would be great if someone could answer.

Answer 1

First I will just give an explanation of what the return trip means. I also posted this answer here .

Recursion means calling a function from the same function. Now it happens that when a function encounters a call to itself ... imagine that a new page is opened, and control is transferred from the old page to this new page before the function starts, when the function encounters a call in this new page, another page opens nearby, and thus new pages appear next to the old page. Please note that all local variables are only in the area with the corresponding pages. That is, if you want to access the value on the previous page, you either pass it to the function in the parameters, or make the variable global.

The only way to return is to use the return statement. When a function encounters this, the control jumps from the new page back to the old page on the same line from where it was called, and starts to do everything below that line. This is where the countdown begins. In order to avoid problems associated with data submission when they are filled, you usually need to put a return statement after each function call.

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. This is local. This means that each time you call it reset. To avoid this, you again pass the value of the path in the function parameters (in the last).

So, when the function returns after it has found d , it will return to the previous state, where the path variable has only a, b, c . what you print.

Edit: - Just in case anyone objects, my explanation of recursion using pages is purely non-technical, if you want to know how this actually happens, you will need to read about activating the record and how it pushes everything state on stack

Answer 2

This is because recursion yields results from the “innermost” to the “outer” calls. This first line of 17 print runs from the deepest recursion level, where the path has the most nodes. After this level, the next level is returned "up" (one node less on the way). Note that your print function appears after a 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 single (sub-) paths to be printed in increasing order, you can simply put the print function before a recursive call on find_path .

This is the new_path variable, which contains the recursively found path, and path simply contains the path to the current node.

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

Answer 3

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

2) Calling the find_path method with b as the starting node sets the path as ['a','b'] and calls the find_path method with c as the beginning of the node to the print path to line 17.

3) Calling the find_path method with c as the start of the node sets the path as ['a','b','c'] and calls the find_path method with d as the start of the node to the print path to line 17.

4) Calling the 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 when executing the find_path method with c as the start of the node (which set the path as ['a','b','c'] , as mentioned in step 3), and prints the path on line 17 (this is the 5th row of your result) and returns.

6) This returns on line 14 when the find_path method is find_path with b as the start of the node (which set the path as ['a','b'] , as indicated in step 2), and prints the path on line 17 (which is line 6 from your result) and returns.

7) This returns on line 14 when the find_path method is find_path with a as the start of the node (which set the path as ['a'] , as indicated in step 1), and prints the path on line 17 (which is line 6 of your result) and returns.

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