开发者

Recursive method will not move on and remains in an infinite loop (Java )

I'm learning about recursion as part of a Java tutorial and I am looking for a little help.

We need to make a recursive Java program which will work out how to get from one city to the other when there is no direct flight.

My problem is that Im getting an infinite loop that only seems to try two cities and then the code repeats itself again and again.

I would appreciate some help on this if you could.

I do not want to overflow you guys with code so i'll put up the method that you should need. If you need more I will happily add some more code.

public boolean determineRoute(City from, City to, ArrayList<City> flightRoute) {

    int i = 0开发者_运维知识库;

    ArrayList<City> Connections = new ArrayList<City>();

    // the Connections value takes all the connecting cities we can travel to from a departure point
    Connections = from.getConnections();

    // searches in the connecting cities from the current city as to if it contains the city we wish to travel to
    if (Connections.contains(to)) {
        System.out.println("Congrats you can go their cause one of its connecting cities is the to city that u wanna go to");
        return true;
    } else {
        // add connecting city to list for future reference
        flightRoute.add(Connections.get(i));
        System.out.println(Connections.get(i) + " added to flight route");
        // saves current connection
        City theCity = Connections.get(i);
        // recursive part which sends a new from city for analysis until the city we want to travel to arises
        determineRoute(from = Connections.get(i), to, flightRoute);
        return true;
    }

}


Just a hint: Do you think it is appropriate to have a city twice on the route? You are currently building such flight routes.


This code makes no sense whatsoever.

Variable i is never incremented. The only one of the connections of a city will ever be used. Why are you setting from in the recursive call?

Why are you creating an array list simply to overwrite the only reference to it in the next line?

What you want is Dijkstra's algorithm. This algorithm is iterative and will find the shortest path length, which could be lowest cost, fewer changes or shortest duration.


Detect the cycle and break it.

You have cursed yourself with the one thing that kills any recursive method: you don't have a stopping condition.

Before you add a city to the list of connections, check to see if it already appears. If it does, there's no need to add it again by recursing.

You keep recreating the list of Connections each time you enter the method, so the previous call's values are forgotten each time. You can prove this quickly by firing up a debugger and adding a breakpoint at the start of your method. You'll see that the connections list is empty each time you enter the method.

A better solution would be to pass that list into the method so new values can be appended to the growing list each time.


In short: the recursive method will stop recursing only when Connections contains the city you want to go to. Since nothing is ever added to Connections, this will never become true, if it's not true initially.

You've got sort of the same issue with the variable i: its value never changes, so again, nothing different ever happens.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜