writing a recursive method into a non recursive (java)

Question

I'm a little bit confused as to understanding how recursion works.

Basically I have to replace recursive methods with non recursive methods.

For example, this is the recursive method:

public Key min() {
    if (isEmpty()) {
        return null;
    }
    return min(root).key;
}

private Node min(Node x) {
    if (x.left == null) {
        return x;
    } else {
        return min(x.left);
    }
}

public Key max() {
    if (isEmpty()) {
        return null;
    }
    return max(root).key;
}

private Node max(Node x) {
    if (x.right == null) {
        return x;
    } else {
        return max(x.right);
    }
}

public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) {
        return null;
    } else {
        return x.key;
    }
}

private Node floor(Node x, Key key) {
    if (x == null) {
        return null;
    }
    int cmp = key.compareTo(x.key);
    if (cmp == 0) {
        return x;
    }
    if (cmp < 0) {
        return floor(x.left, key);
    }
    Node t = floor(x.right, key);
    if (t != null) {
        return t;
    } else {
        return x;
    }
}

public Key ceiling(Key key) {
    Node x = ceiling(root, key);
    if (x == null) {
        return null;
    } else {
        return x.key;
    }
}

private Node ceiling(Node x, Key key) {
    if (x == null) {
        return null;
    }
    int cmp = key.compareTo(x.key);
    if (cmp == 0) {
        return x;
    }
    if (cmp < 0) {
        Node t = ceiling(x.left, key);
        if (t != null) {
            return t;
        } else {
            return x;
        }
    }
    return ceiling(x.right, key);
}

And this is my attempt of doing it non-recursively:

public Key min() {
    if (isEmpty()) {
        return null;
    }
    return min(root).key;
}

private Node min(Node x) {

    while (x.left !=null){
         x = x.left; 
    }
    return x;
}

public Key max() {
    if (isEmpty()) {
        return null;
    }
    return max(root).key;
}

private Node max(Node x) {
    while (x.right!=null){
        x = x.right;
    }
    return x;
}

public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) {
        return null;
    } else {
        return x.key;
    }
}

private Node floor(Node x, Key key) {
    if (x == null) {
        return null;
    }
    int cmp = key.compareTo(x.key);
    if (cmp == 0) {
        return x;
    }
    if (cmp < 0) {
        while (x.left != null){
            x = x.left;
            if (x ==null){
                return null;
            }
        }
    }
    Node t = x.right;
    while (x.right != null){
        x = x.right;
        if (x == null){
            return null;
        }
    }
    if (t != null){
        return t;
    }
    else{
        return x;
    }
}

I'm just asking if I have the right idea.

1. Links invalid 2. you should post code directly in your post. — August, Nov 14 '14 at 01:44
The links you've provided don't appear to work. It looks like it's because they include the SO citation brackets at the end. The code should still be posted here regardless. — pseudoramble, Nov 14 '14 at 01:44

score 0 · Answer 1 · edited May 23 '17 at 11:57

Yes, you have the right idea.

private Node min(Node x) {
    if (x.left == null) {
        return x;
    } else {
        return min(x.left);
    }
}

This is good non-recursive solution of the function above.

private Node min(Node x) {

    while (x.left !=null){
         x = x.left; 
    }
    return x;
}

You should take a look at http://en.wikipedia.org/wiki/Dynamic_programming, particularly Memoization.

Edit: Also take a look at similar thread: Way to go from recursion to iteration

writing a recursive method into a non recursive (java)

1 Answers1