Преобразование цикла while в рекурсию в Java - PullRequest
Новая
       38

Преобразование цикла while в рекурсию в Java

0 голосов
/ 29 сентября 2019

Привет, я пытаюсь преобразовать этот код Java в то время как код цикла в рекурсию.Я пытался преобразовать его в рекурсию, но получаю сообщение об ошибке.цикл while работает нормально только тогда, когда я конвертирую его в рекурсию, когда я получаю ошибку.Буду признателен за любую помощь в том, как преобразовать его в рекурсию, спасибо. 

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;

}

// код рекурсии 

    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;
    }

1 Ответ

0 голосов
/ 29 сентября 2019

Похоже, вы проверяете только немедленные циклы в своей первой итеративной версии.(Вы не проверяете, есть ли у вас петля большего размера A -> B -> C -> A. Вы проверяете только петли типа A -> B -> A).Я предполагаю, что то, что вы представили, правильно и что вы хотите, хотя и странно.(Если у вас большой цикл, он будет продолжаться бесконечно).

Правильный и простой способ сделать то, что вы представили рекурсивно: 

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());
   }
}

Если вы хотите, чтобы он проверялвсе возможные циклы, которые вам понадобятся, чтобы сделать это немного по-другому: 

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>());
}

Это проверит все узлы seen, если они снова появятся в ссылке next.Это на самом деле использует .equals() и .hashCode() вашего Node, поэтому важно, чтобы они реализовывались согласованно друг с другом.

...