Breadth-first search (recursive)

"""
This is a stupid way to do BFS because there's no reason to do a recursive call instead of just having a while loop. It's maybe useful just to make it clear why recursion isn't needed for BFS and to make a person slightly more confident with recursion / BFS.

Common mistakes:
- I forgot the base case.
"""
from collections import deque

def bfs_r(graph, start):
    visited = set()
    queue = deque([start])
    return bfsr_helper(graph, queue, visited)

def bfsr_helper(graph, queue, visited):
    # We need to do this check because we'll get an error if we try to pop from
    # an empty deque rather than a None return value:
    if not queue:
        return  # Base case: if the queue is empty, return

    vertex = queue.popleft()  # Dequeue the first node in the queue
    if vertex not in visited:
        print(vertex, end=" ")  # Process the current node
        visited.add(vertex)  # Mark the current node as visited

        # Add all unvisited neighbors to the queue
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)

    bfsr_helper(graph, queue, visited)  # Recursive call with the updated queue

graph = {
    1 : [2,3],
    2 : [4, 5],
    3 : [5],
    4 : [],
    5 : [1],
}

bfs_r(graph, 1) # Start BFS from vertex 1