Finding path from point A to point B using recursion in Python

{'John': ['Bryant', 'Debra', 'Walter'], 'Bryant': ['Olive', 'Ollie', 'Freda', 'Mercedes'], 'Mercedes': ['Walter', 'Robin', 'Bryant'], 'Olive': ['John', 'Ollie'], 'Debra': ['Walter', 'Levi', 'Jennie', 'Robin'], 'Walter': ['John', 'Levi', 'Bryant'], 'Levi': ['Ollie', 'John', 'Walter'], 'Ollie': ['Mercedes', 'Freda', 'Bryant'], 'Jennie': ['Levi', 'John', 'Freda', 'Robin'], 'Robin': ['Ollie'], 'Freda': ['Olive', 'John', 'Debra']}

The dictionary is the user and their corresponding connections.

I have to define a function that finds a connection path from a userA to userB and return the path in a list using recursion. It should also return None if no path exists but I don’t know how to achieve that.

Example Input: "John", "Freda"
Output: ["John", "Bryant", "Freda"]

This my attempt but it raises a RecursionError:

def find_path_to_friend(network, user_A, user_B):
    path = [user_A]
    connections = network[user_A]["is connected to "]
    if user_B in connections:
        path.append(user_B)
        return path
    for i in connections:
        return find_path_to_friend(network, i, connections)

>Solution :

Here is my solution with BFS. You can also write recursive programs for that but as BFS is not usually implemented recursively, I wrote it this way. But if you insist on recursion, I can change it:

from collections import defaultdict


def find_path_to_friend(network, src, dest):
    queue = [src]
    visited = defaultdict(bool)
    path = []
    while len(queue) != 0:
      node = queue.pop(0)
      path.append(node)
      visited[node] = True
      if node in network:
        for adj in network[node]:
          if adj == dest:
            return path + [dest]
          if not visited[adj]:
            queue.append(adj)
    return None

network = {'John': ['Bryant', 'Debra', 'Walter'], 'Bryant': ['Olive', 'Ollie', 'Freda', 'Mercedes'], 'Mercedes': ['Walter', 'Robin', 'Bryant'], 'Olive': ['John', 'Ollie'], 'Debra': ['Walter', 'Levi', 'Jennie', 'Robin'], 'Walter': ['John', 'Levi', 'Bryant'], 'Levi': ['Ollie', 'John', 'Walter'], 'Ollie': ['Mercedes', 'Freda', 'Bryant'], 'Jennie': ['Levi', 'John', 'Freda', 'Robin'], 'Robin': ['Ollie'], 'Freda': ['Olive', 'John', 'Debra']}
print(find_path_to_friend(network, 'John', 'Freda'))
# ['John', 'Bryant', 'Freda']

Here is the recursive approach to eliminate the outer for loop in BFS:

def find_path_to_friend(network, src, dest):
    visited = defaultdict(bool)
    def rec(queue):
      if len(queue) == 0:
        return []
      node = queue.pop(0)
      path = [node]
      visited[node] = True
      if node in network:
        for adj in network[node]:
          if adj == dest:
            return path + [dest]
          if not visited[adj]:
            queue.append(adj)
      return path + rec(queue)
    queue = [src]
    return rec(queue)