Confused about recursion in python-depth first search-:

S

shivajikobardan

Junior Member
Joined
Nov 1, 2021
Messages
107
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)



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?
 
shivajikobardan said:
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)



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?
Click to expand...
After visiting node '1' the program returns to where it came from, i.e. node '19' and goes on to the next child, which is '12'.

Don't be to hard on yourself: you are not stupid, but getting used to recursive algorithm takes time. They used to drive me crazy too. Just get more practice with them and you will see they can be very elegant.
 
shivajikobardan said:
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)



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?
Click to expand...
dfs(7) calls dfs(19). dfs(7) itself does not go away, it's still around, waiting for dfs(19) to return. Same for dfs(19) calling dfs(1). As soon as dfs(1) returns dfs(19) executes the next loop iteration: dfs(12). And when dfs(19) returns dfs(7) will continue to dfs(21).
 
blamocur said:
After visiting node '1' the program returns to where it came from, i.e. node '19' and goes on to the next child, which is '12'.
Click to expand...
That totally confuses the flow of program to me. imo it should've been stopped there as there is no more function calling. how does it goes to do dfs(12)...Is there a reason or some dummy example to understand this properly?
 
lev888 said:
dfs(7) calls dfs(19). dfs(7) itself does not go away, it's still around, waiting for dfs(19) to return. Same for dfs(19) calling dfs(1). As soon as dfs(1) returns dfs(19) executes the next loop iteration: dfs(12). And when dfs(19) returns dfs(7) will continue to dfs(21).
Click to expand...
do you have some visual representation(not you making sth that is already there) about this?
I understand what you are saying but as I said, after dfs(1) happens and print(1) happens. code should've stopped. I don't understand why we continued after that and how we continued.
 
shivajikobardan said:
do you have some visual representation(not you making sth that is already there) about this?
I understand what you are saying but as I said, after dfs(1) happens and print(1) happens. code should've stopped. I don't understand why we continued after that and how we continued.
Click to expand...
Let's say dfs() calls dfs2() which is a copy of dfs. Do you see that after dfs2() returns dfs() would continue executing the loop? Same thing happens in recursion. dfs(7) call stays in memory while a copy of dfs executes. And that copy stays in memory while another copy executes:

dfs(7) -> dfs(19) -> dfs(1) - they are all in computer memory at the same time. After dfs(1) stops control goes to dfs(19), etc.
 
shivajikobardan said:
do you have some visual representation(not you making sth that is already there) about this?
I understand what you are saying but as I said, after dfs(1) happens and print(1) happens. code should've stopped. I don't understand why we continued after that and how we continued.
Click to expand...
It does not stop, it returns to the previous instance of itself. As the program calls itself it leaves its context on the stack, so when it returns from node 1 to node 19 it remembers the context and knows that it has to go to node 12.

Here is another way to thing of this: imagine that you have 3 identical programs (where 3 is the depth of the graph): dfs1, dfs2 and dfs3.
  • dfs1 visits node 7, and calls dfs2 on node 19.
  • dfs2 visits node 19 and calls dfs3 on node 1.
  • dfs3 visits 1 finds nothing to do and returns do dfs2
  • dfs2 is done with 1 and moves on to node 12.
  • ...
Something similar happens at runtime: while the code of 'dfs' is the same the sets of local variables stay on the stack, so the execution is equivalent to the sequence described above. But it helps to think that a compiler creates a separate copy of the program for each call level.
 
Last edited:
You must log in or register to reply here.
Top