Compilation error while implementing the Depth first search Recursively

Question

I am new to using recursion for my methods. I tend to steer away from them for quite a few reasons. However, for a project, it seems to easier to have a recursive method instead of a looping one since I am trying to do Depth First Traversal for a Graph.

Since I am not too well versed in recursion, I don't understand why I am getting the following error.

This method must return a result of type LinkedList.Node

The code I have currently is:

public Node DFSTime(Node node){
    if(node == null){
        System.out.println("No path found");
        return null;
    }
    else if(node.element.equals(destinationAirport)){
        return node;
    }
    else{
        stack.push(node);
        DFSTime(node.nextNode);            
    }
}

It is unfinished code since I still need to implement some logic, however, I don't understand how to eliminate the error. Is there something very basic that I am missing?

Answer 1

The reason of the compilation error is pretty trivial. The compiler clearly tells that didn't provide the result to return for all possible cases.

The more important is that your current approach is not correct.

it seems to easier to have a recursive method instead of a looping one since I am trying to do Depth First Traversal for a Graph

There are crucial things to consider:

• Field nextNode is very suspicious. If each Node holds a reference pointing to a single node only, in fact the data structure you've created by definition isn't a Graph, but a Singly linked list. And doesn't make sense to implement DFS for a list. Every node should point to a collection of nodes, no to a single node.

• You have to distinguish somehow between unvisited nodes and nodes that are already visited. Or else you might and up with infinite recursion. For that, you can define a boolean field isVisited inside the Node, or place every visited node into a HashSet.

• Since you've chosen to create a recursive implementation of DFS, you don't need to create a stack. It's required only for iterative implementation.

• Don't overuse global variables. I guess you might want to be able to check whether it is possible to reach different airports of destination without reinstantiating the graph.

• Use getters and setters instead of accessing fields directly. It's a preferred practice in Java.

Your method might look like this (it's not necessary that element should be of type String it's just an illustration of the overall idea):

public Node DFSTime(Node node, String destinationAirport){
    if(node == null || node.isVisited()) {
        return null;
    }
    if (node.getElement().equals(destinationAirport)) {
        System.out.println("The destination airport was found");
        return node;
    }
    
    node.setVisited(true);
    for (Node neighbour: node.getNeighbours()) {
        Node result = DFSTime(neighbour, destinationAirport);
        if (result != null) return result;
    }
    return null;
}

And the node might look like this:

public class Node {
    private String element;
    private List<Node> neighbours;
    private boolean isVisited;
    
    public Node(String element, List<Node> neighbours) {
        this.element = element;
        this.neighbours = neighbours;
    }
    
    public void setVisited(boolean visited) {
        isVisited = visited;
    }
    
    public boolean isVisited() {
        return isVisited;
    }
    
    public void addNeighbours(Node neighbour) {
        neighbours.add(neighbour);
    }
    
    public String getElement() {
        return element;
    }
    
    public List<Node> getNeighbours() {
        return neighbours;
    }
}