CODEWITHSUNDEEP
javarecursiondata-structures
DaGuyWhoCodes
DaGuyWhoCodes

Reputation: 13

Converting while loop to recursion in java

Hi I'm trying to convert this java while loop code into recursion. I have tried converting it into recursion but I keep getting an error. the while loop works fine is just when I convert it into recursion is when I get an error. Any help on how to convert it into recursion will be appreciated, Thank you.

public static boolean hasCycle( Node head) {
    Node slow = head;
    Node fast = head; 
    boolean loop = false; 
    while (slow != null && fast != null && fast.getNext() != null) {
        slow = slow.getNext();
        fast = fast.getNext().getNext();

        if(slow == fast) {
            loop = true;
            break;
        }
    }
    return loop;

}

//recursion code

    Node slow = head;
    Node fast = head; 
    boolean loop = false; 

    if(slow == fast) {
        return true;
    }else if(slow != fast) {
        if(slow.getNext() != null) {
            return hasCycle(slow.getNext());
        }
        return false;
    }else {
        if(fast.getNext() != null) {
            return hasCycle(fast.getNext());
        }
        return false;
    }

Upvotes: 0

Views: 136

Answers (1)

jbx
jbx

Reputation: 22128

You seem to only be checking for immediate loops in your first iterative version. (You are not checking if you have a larger loop A -> B -> C -> A. You are only checking for loops like A -> B -> A). I assume that what you presented is correct and what you want, albeit strange. (If you have a larger loop it will go on infinitely).

The proper and simpler way to do what you presented recursively is: 

public boolean hasImmediateCycle(Node node) {
   if (node == null || node.getNext() == null) {
      return false;
   } else if (node == node.getNext().getNext()) {
      return true;
   } else {
      return hasImmediateCycle(node.getNext());
   }
}

If you wanted to make it check for all possible loops you would need to do it slightly differently:

private boolean hasCycle(Node node, Set<Node> seen) {
   if (node == null) {
      return false;
   } else if (seen.contains(node)) {
      return true;
   } else {
      seen.add(node);   
      return hasCycle(node.getNext(), seen);
   }
}

public boolean hasCycle(Node node) {
  return hasCycle(node, new HashSet<Node>());
}

This will check all the seen nodes in case they appear again in the next reference. This actually uses the .equals() and .hashCode() of your Node so it is important they are implemented consistently with each other.

Upvotes: 1

Related Questions