Recursively finds a TSP path by always visiting the nearest unvisited city, and finally returning to the start.

# TSP Greedy Recursive
# Description: Recursively finds a TSP path by always visiting the nearest unvisited city, and finally returning to the start.

def find_nearest_unvisited_city(current_city, dist, visited):
    """
    Find the nearest unvisited city from the current city.

    Args:
        current_city (int): Index of the current city
        dist (list of list): Distance matrix
        visited (list): Boolean array tracking visited cities

    Returns:
        int or None: Index of the nearest unvisited city, or None if all cities visited
    """
    nearest_city = None
    shortest_distance = float('inf')

    for city in range(len(dist)):
        if not visited[city] and dist[current_city][city] < shortest_distance:
            shortest_distance = dist[current_city][city]
            nearest_city = city

    return nearest_city

def tsp_greedy_recursive(dist):
    """
    Solve the Traveling Salesman Problem using a greedy recursive approach.

    Finds a route by always visiting the nearest unvisited city and 
    returning to the starting point. This is a heuristic approach 
    that does not guarantee the optimal solution.

    Args:
        dist (list of list): Distance matrix where dist[i][j] 
                              represents the distance from city i to city j

    Returns:
        list: Route (list of city indices) representing the greedy TSP path

    Example:
        distances = [
            [0, 10, 15, 20],
            [10, 0, 35, 25],
            [15, 35, 0, 30],
            [20, 25, 30, 0]
        ]
        route = tsp_greedy_recursive(distances)
        # Possible output: [0, 1, 3, 2, 0]
    """
    def recursive_tsp_helper(current_city, visited, route):
        """
        Recursive helper function to build the TSP route.

        Args:
            current_city (int): Current city being visited
            visited (list): Boolean array tracking visited cities
            route (list): Current route of cities

        Returns:
            list: Complete route including return to start
        """
        # Mark current city as visited and add to route
        visited[current_city] = True
        route.append(current_city)

        # Find the nearest unvisited city
        next_city = find_nearest_unvisited_city(current_city, dist, visited)

        # If no unvisited cities remain, return to start
        if next_city is None:
            route.append(route[0])
            return route

        # Recursively continue the route
        return recursive_tsp_helper(next_city, visited, route)

    # Initialize tracking for visited cities and route
    num_cities = len(dist)
    visited = [False] * num_cities
    route = []

    # Start the recursive TSP from city 0
    return recursive_tsp_helper(0, visited, route)