3 ms·

Confused about recursion in Python-depth first search

[CODE=python] # Python dictionary to act as an adjacency list graph = { '7' : ['19','21', '14'], '19': ['1', '12', '31'], '21': [], '14': ['23', '6'], '1' : [], '12': [], '31': [], '23': [], '6' : [] } visited = [] # List of visited nodes of graph. def dfs(visited, graph, node): if node not in visited: visited.append(node) for neighbor in graph[node]: dfs(visited, graph, neighbor) print(node) # Driver Code print("Following is the Depth-First Search") dfs(visited, graph, '7') print("visited=",visited) [/CODE] what I don't understand is how do once this program reaches to print(1) what happens next, it doesn't make any sense to me. idk if I am stupid or what to not realize sth very trivial or idk. I will try to explain what is my problem, step by step. steps-: 1) dfs(visited,graph,7) 2) 7 not in visited. visited=7 dfs(19) 3) 19 not in visited. visited=7,19 dfs(1) 4) 1 not in visited visited=7,19,1 1 has no neighbours. print(1) imo the code should stop now. Because there is no function call no nth. But in fact the code goes to for neighbour in graph(node): dfs(visited,graph,neighbour) and starts with dfs(12). I don't understand this....How does it happen? how can it go to for loop just like that?(source-:https://cscircles.cemc.uwaterloo.ca/visualize#mode=display) even if it doesn't go to for loop, I can't make sense where it really goes. Can you please guide me about this issue?

tgflynn 5y ago
It doesn't stop at 1 because the previous function call (dfs(19)) hasn't finished processing its neighbor list yet. If you're wondering "how does it know that" it's because each function call creates a stack frame to keep track of its state (ie. arguments, temporary variables, etc.). When a function call returns the stack frame of its caller is essentially restored. Recursion can be a tough concept to grasp the first time you encounter it (and sometimes even for a while after that). I would suggest that you work with a simpler recursive function (dfs is a somewhat advanced example), like, for example, factorial until you understand exactly what's going on. Use print statements to see when each function call happens, when it returns and what its arguments are. Secondly you should try to find a ressource that explains how function calls and stack frames work. I don't know of any off the top of my head but I'm sure if you do some Googling you'll find what you need.

tgflynn 5y ago

It doesn't stop at 1 because the previous function call (dfs(19)) hasn't finished processing its neighbor list yet. If you're wondering "how does it know that" it's because each function call creates a stack frame to keep track of its state (ie. arguments, temporary variables, etc.). When a function call returns the stack frame of its caller is essentially restored. Recursion can be a tough concept to grasp the first time you encounter it (and sometimes even for a while after that). I would suggest that you work with a simpler recursive function (dfs is a somewhat advanced example), like, for example, factorial until you understand exactly what's going on. Use print statements to see when each function call happens, when it returns and what its arguments are. Secondly you should try to find a ressource that explains how function calls and stack frames work. I don't know of any off the top of my head but I'm sure if you do some Googling you'll find what you need.