Confused about recursion in python-depth first search-:

In summary, the code goes to dfs(12) because node is not in visited list for graph and then it prints 1.
  • #1
shivajikobardan
674
54
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?
 
Technology news on Phys.org
  • #2
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]
 
  • #3
Jameson said:
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]
yes you are right about visited. but I don't understand how once print(1) happens, how it returns to dfs(19)=>dfs(12)...can you explain that?
 
  • #4
Jameson said:
Check your indentation of the for loop. It is currently in line with the if block but you want to run it only if that condition is false right? Also it shouldn't stop at 1 completely but it will partially stop at 1.

I think it should go visited = [7,19,1,12,31...]
1643780608888.png


in the slide instead of printing visited, we have printed node...what does that mean? shouldn't output of depth first search be how we traverse? i m not getting this last point.

slide is here(view in desktop) https://slidetodoc.com/tree-and-graph-traversal-algorithms-breadthfirst-search-bfs/
 

1. What is recursion in Python?

Recursion in Python is a programming technique where a function calls itself until a certain condition is met. It is a useful tool for solving problems that can be broken down into smaller, similar subproblems.

2. How does depth first search work?

Depth first search is a graph traversal algorithm that explores a graph by going as deep as possible in each branch before backtracking. It starts at a given node and explores its adjacent nodes, repeating the process until all nodes have been visited.

3. What is the difference between recursion and iteration?

Recursion and iteration are both ways of repeating a process. The main difference is that recursion involves calling a function within itself, while iteration uses looping structures to repeat the process.

4. How do you implement recursion in Python?

To implement recursion in Python, you need to define a function that calls itself and has a base case to stop the recursion. The function should also have a way to reduce the problem into smaller subproblems until the base case is reached.

5. What are the advantages of using recursion?

Recursion can make complex problems easier to solve by breaking them down into smaller, simpler subproblems. It also allows for more concise and readable code in certain situations. However, it can be less efficient and may lead to stack overflow errors if not implemented correctly.

Similar threads

  • Programming and Computer Science
Replies
1
Views
687
  • Programming and Computer Science
Replies
1
Views
965
  • Engineering and Comp Sci Homework Help
Replies
2
Views
948
  • Engineering and Comp Sci Homework Help
Replies
2
Views
799
  • Programming and Computer Science
Replies
2
Views
625
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Programming and Computer Science
Replies
9
Views
2K
  • Programming and Computer Science
Replies
7
Views
423
  • Programming and Computer Science
Replies
19
Views
2K
  • Programming and Computer Science
Replies
4
Views
2K
Back
Top