def all_routes(cities, i=0):
    """Return all possible routes, where cities[i:] have been permuted.

    Args:
        cities (list of string):
            The cities that make up each route.

        i (int, optional):
            The starting index of the subarray of cities to be permuted.

    Returns:
        list of tuple of string: The list of all possible routes.
    """
    # Base Case: Routes should be immutable tuples, not mutable lists.
    if i >= len(cities) - 1:
        return [tuple(cities)]

    # Inductive Step: Swap in each possible starting city.
    routes = []
    for j in range(i, len(cities)):
        cities[i], cities[j] = cities[j], cities[i]
        routes.extend(all_routes(cities, i + 1))
        cities[i], cities[j] = cities[j], cities[i]

    return routes