how to do this java recursive

Question

I have this code:

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

The problem with this method is I must declare countStu outside the countStudent() method, which is not good in the case when I want to call countStudent() twice, it will make the returned value doubles. How do I solve this problem and able to call countStudent() unlimited times with correct results?

Answer 1

Change:

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

    return countStu;

to

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

Answer 2

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

Answer 3

Assuming that this is your homework and you really must declare countStu outside (you shouldn't in any normal code), you can simply wrap the value in some class. Add set+get accessors and pass the object as a second argument to the function. Use it then, instead of the global / static variable.

Or simply don't use the variable at all and return the result + 1. Not sure if this is allowed by your rules.

Answer 4

In general when you are trying to do something like is useful to try to remove the explicit state handling somehow.

For example if you have to compute a function f(x) = G(f(x-1)) you can express G as a stateless method and follow the following pattern:

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

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

That way you don't have any side effects like you have with your current code. The downside is usually minor compared with what you are doing right now (the same stack depth is used overall).

The important thing is to make sure the G and F implementations are stateless (not using variables declared outside the method body scope).

Answer 5

Holding the state of the recursion in the static field would not be thread-safe. Instead hold the value in the stack.

I give you both a recursive example which would risk a StackOverflowError with as little as 6k nodes with a default heap as well as a loop version which doesn't suffer from this.

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

why do i need to call again this , if lst.getNext() has null. precompute before calling recursion, there are different types.when u call this method countStudent from main method , check the lst value for not null , before recursion starts.

public static int countStudent(Node lst) {

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