How recursive inner static class get initialized?

157 views Asked by At

i was looking into Trie data-structure and came across this piece of code

// R-way trie node
    private static class Node {
        private Object val;
        private Node[] next = new Node[26];
    }

i understood the logic, but what i don't get is, to what depth the Node will get initialized ?

you can check complete code at http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/TrieST.java.html

2

There are 2 answers

0
Eran On BEST ANSWER

There is no recursion here.

private Node[] next = new Node[26];

doesn't create any Node instance. It creates a Node[] (array of Node references) of 26 elements. All the references are initialized to null. The Node instances referenced by the array must be initialized elsewhere.

If, on the other hand, you had a member initialized as:

private Node n = new Node ();

that would cause an infinite recursion once the first instance of Node would be created.

0
K.Suthagar On

In your code Lines, First you are inserting values using put(val1,val2) command in main method.

st.put(key, i);

Code lines for the put(val1,val2) method below,

 public void put(String key, Value val) {
        if (val == null) delete(key);
        else root = put(root, key, val, 0);
    }

according this code lines, the recursive else part is calling another put(val1,val2,val3,val4) method

Code line for the put(val1,val2,val3,val4) method below,

private Node put(Node x, String key, Value val, int d) {
        if (x == null) x = new Node();
        if (d == key.length()) {
            if (x.val == null) n++;
            x.val = val;
            return x;
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, val, d+1);
        return x;
    }

Here, when x==null then Node objects are initializing using new Node();.