CODEWITHSUNDEEP
javarecursionstacksize
skulpt
skulpt

Reputation: 527

Java: return self-made stack size using recursion

So I've been going over some assignments I had in class when I noticed something on one I've turned in. Part of it was writing a stack and a node class, which should have a method to return the stack's current size. I missed out on the fact that I actually needed to use recursion in the size method. So I've tried something and I got the right results. Here's the code:

public class CharStack {

    private CharStackNode top;

    public CharStack() {
        top=null;
    }

    public void push(char img) {
        CharStackNode node=new CharStackNode(img, top);
        top=node;
    }

    public char pop() {
        char result = top.getImage();
        top = top.getNext();
        return result;
    }

    public char peek() {
        return top.getImage();
    }

    public int size() {
        int counter=0;
        if(this.top!=null) {
        counter=this.top.size();
        }
        return counter;
    }

    public boolean empty() {
        return top == null;
    }
}

So as you can see, I'm calling the node's size method to actually determine the size. Here's the node class:

public class CharStackNode {

    private char image;
    private CharStackNode next;

    public CharStackNode(char image, CharStackNode next) {
        this.image = image;
        this.next = next;
    }

    public char getImage() {
        return image;
    }

    public CharStackNode getNext() {
        return next;
    }

    public int size() {
        int count=0;
        if(this.next!=null) {
            count=this.next.size();
        }
        count+=1;
        return count;
    }
}

As you can see, I'm doing the recursive part in the node's size method. However, the assignment basically implies not to use an extra size method in the node class (all the other methods I've made can be used though). And there's my problem - I don't have any idea how to implement it in any other way while still using recursion.

Thanks in advance for any help.

Upvotes: 0

Views: 667

Answers (2)

Aify
Aify

Reputation: 3537

You can call the recursive function from your own stack class instead of from the node class. It's possible to get the size using a loop instead of recursion.

Calling from the stack with your code (Call this with top as the parameter):

public int size(CharStackNode node) {

    // check to see if this node is null
    if (node == null) {
        return 0;
    }

    // call this function with the next node as the parameter
    tempInt = size(node.getNext());

    return  tempInt + 1;
}

Upvotes: 0

John Bollinger
John Bollinger

Reputation: 181724

You can implement the required recursion on a private method of your stack class, with the size() method used merely as a front end. That will allow you to define whatever arguments you need to control the recursion. For instance, you might implement a recursive method like this:

private int tailSize(CharStackNode from) {
    return (from == null) ? 0 : (1 + tailSize(from.getNext()));
}

and write your CharStack.size() as

public int size() {
    return tailSize(top);
}

Note that recursion is a crummy way to solve this particular problem. An iterative solution has less overhead and is not particularly more complicated:

public int size() {
    int rval = 0;

    for (CharStackNode next = top; next != null; next = next.getNext()) {
        rval += 1;
    }

    return rval;
}

Upvotes: 1

Related Questions