1
def find_itinerary(start_city, start_time, end_city, deadline):
    discovered = set()
    depth = 0
    import copy
    def dfs(curr_city,curr_time,flight_tracker):
        if curr_city == end_city:
            return flight_tracker
        for flight in flightDB:
            if flight.end_city not in discovered and flight.match(curr_city,curr_time):
                ft = copy.deepcopy(flight_tracker)
                ft.append(flight)
                dfs(flight.end_city,flight.end_time,ft)
    return dfs(start_city,start_time,[])

The function above always returns None. I know why it returns None (the for loop dfs is not returned) but I dont know how to fix it. Also,I cannot put a return statement within the for loop as it will break the for loop. Is it possible to do recursive DFS that returns a value like a list?

Gary Ong
  • 788
  • 1
  • 5
  • 8
  • 1
    Let's say your dfs does 10 recursive calls before finding the solution. Call #10 will return flight_tracker to Call #9. However Call #9 is not returning anything in your if statement so the foor loop will continue. – Yacine Mahdid Jun 04 '20 at 19:03
  • Yeah but i dont know how to fix it. May be its not possible recursively? – Gary Ong Jun 05 '20 at 02:10
  • I'm not sure with the rest of the code, but for sure you need to have `return dfs(flight.end_city,flight.end_time,ft)` if the rest is working properly. – Yacine Mahdid Jun 05 '20 at 02:55
  • if you return the for loop stops running. I figured the solution was just to pass a reference such as an empty list and at the end just append the solution to the empty list. – Gary Ong Jun 05 '20 at 03:15

0 Answers0