, как это сделать Java рекурсивный

Question

У меня есть этот код:

static int countStu = 0; 

public static int countStudent(Node<Student> lst) { 
    // pre : true 
    // post : res = number of students in list 
    if (lst != null) { 
     countStu++; 
     countStudent(lst.getNext());  
    } 
    return countStu; 
} 

Проблема с этим методом, я должен объявить countStu вне countStudent() метода, который не хорош в том случае, когда я хочу позвонить countStudent() дважды , это приведет к удвоению возвращаемого значения. Как решить эту проблему и позвонить по телефону countStudent() неограниченное время с правильным результатом?

Answer 1

Изменение:

if(lst!=null){ 
countStu++; 
countStudent(lst.getNext());  
} 

    return countStu; 

в

return lst==null ? 0 : (1+countStudent(lst.getNext())); 

Answer 2

вместо return((lst == null)? 0 : (1 + countStudent(lst.getNext()))).

Answer 3

Предполагая, что это ваша домашняя работа, и вы действительно должны объявить countStu снаружи (вы не должны в каком-либо нормальном коде), вы можете просто обернуть значение в каком-то классе. Добавьте set + get accessors и передайте объект в качестве второго аргумента функции. Затем используйте его вместо глобальной/статической переменной.

Или просто не используйте переменную вообще и возвращайте результат + 1. Не уверен, разрешено ли это правилами.

Answer 4

В целом, когда вы пытаетесь сделать что-то вроде полезного, попытайтесь как-то удалить явное управление состоянием.

Например, если нужно вычислить функцию F (X) = G (F (х-1)) можно выразить G в качестве лица без метода и следовать по следующей схеме:

public static ResultType G(ResultType input) { 
    // compute G stateless 
} 

public static ResultType F(int x) { 
    return G(F(x - 1)); 
} 

Таким образом, у вас нет никаких побочных эффектов, как у вас с вашим текущим кодом. Недостаток, как правило, незначительный по сравнению с тем, что вы делаете прямо сейчас (общая глубина стека используется в целом).

Важно, чтобы реализации G и F были безстоящими (не используя переменные, объявленные вне области тела метода).

Answer 5

Сохранение состояния рекурсии в статическом поле не будет потокобезопасным. Вместо этого удерживайте значение в стеке.

Я даю вам и рекурсивный пример, который может привести к StackOverflowError с минимальным количеством узлов 6k с кучей по умолчанию, а также версией цикла, которая не страдает от этого.

public class SO3765757 { 
    public static int countNodeRecursive(Node<?> node) { 
    if(node == null) { 
     debug("node is null"); 
     return 0; 
    } 
    int count = 1 + countNodeRecursive(node.getNext()); 
    debug(count + " = " + node.toString()); 
    return count; 
    } 

    public static int countNodeLoop(Node<?> node) { 
    int count = 0; 
    for(Node<?> currentNode = node; currentNode != null; currentNode = currentNode.getNext()) { 
     count += 1; 
     debug(count + " = " + currentNode.toString()); 
    } 
    return count; 
    } 

    public static void main(String[] args) { 
    int count = 10; 
    if(args.length > 0) { 
     try { 
     count = Integer.parseInt(args[0]); 
     } catch(NumberFormatException e) { 
     } 
    } 
    Node<Student> node = getNodeTest(count); 
    System.out.println("Loop count  = " + countNodeLoop(node)); 
    try { 
     System.out.println("Recursive count = " + countNodeRecursive(node)); 
    } catch(StackOverflowError e) { 
     System.out.println("Recursive count caused " + e.getClass().getName()); 
    } 
    } 

    private static void debug(String msg) { 
    System.out.println("DEBUG:" + msg); 
    } 

    private static <T> Node<T> getNodeTest(int count) { 
    Node<T> prevNode = null; 
    for(int i=0;i<count;i++) { 
     Node<T> node; 
     if(prevNode == null) { 
      node = new NodeImpl<T>(); 
     } else { 
      node = new NodeImpl<T>(prevNode); 
     } 
     prevNode = node; 
    } 
    return prevNode; 
    } 

    private static interface Node<T> { 
    Node<T> getNext(); 
    } 

    private static class NodeImpl<T> implements Node<T> { 
    private final Node<T> next; 

    public NodeImpl() { 
     this.next = null; 
    } 

    public NodeImpl(Node<T> next) { 
     this.next = next; 
    } 

    public Node<T> getNext() { 
     return next; 
    } 
    } 

    private static interface Student { 
    } 
} 

Answer 6

countStudent(lst.getNext()); 

почему мне нужно позвонить еще раз в этом, если lst.getNext() имеет нуль. precompute перед вызовом рекурсии, существуют разные типы. Когда u вызывает этот метод countStudent из основного метода, проверьте значение lst для не null, прежде чем начнется рекурсия.

открытые статические INT countStudent (Node LST) {

countStu++; 
    Node<Student> _tmp; 
    _tmp = lst.getNext(); 
    if (_tmp != null) 
     countStudent(lst.getNext());   
    return countStu;  }