How to convert the below recursive functions to for loop iterations

Question

Iterator words = treeSearch.getItems().iterator();

int addCount = 0;
while (words.hasNext())
{
    numWords++;
    rootNode = add(objectToReference, addCount++, (ITreeSearch) words.next(), 0, rootNode);
}


//Add to the Tree
private TernaryTreeNode add(Object storedObject, int wordNum, ITreeSearch treeSearch, int pos, TernaryTreeNode parentNode) throws NoSearchValueSetException
{

    if (parentNode == null)
    {
        parentNode = new TernaryTreeNode(treeSearch.getNodeValue(pos));
    }


    if (parentNode.lessThan(treeSearch, pos))
    {
        parentNode.left = add(storedObject, wordNum, treeSearch, pos, parentNode.left);
    }
    else if (parentNode.greaterThan(treeSearch, pos))
    {
        parentNode.right = add(storedObject, wordNum, treeSearch, pos, parentNode.right);
    }
    else
    {
        if (pos < treeSearch.getNumberNodeValues())
        {
            parentNode.mid = add(storedObject, wordNum, treeSearch, pos + 1, parentNode.mid);
        }
        else
        {
            numberOfObjectsStored++;
            parentNode.addStoredData(storedObject);
        }
    }

return parentNode;
}

This a snippet of my code in my Ternary Tree which I use for inserting a Name of a person(can hav multiple words in a name, like Michele Adams, Tina Joseph George, etc). I want to convert the above recursion to a for loop / while iterator.

Please guide me on this.

score 1 · Answer 1 · answered Oct 28 '14 at 19:03

General idea in replacing recursion with iteration is to create a state variable, and update it in the loop by following the same rules that you follow in your recursive program. This means that when you pick a left subtree in the recursive program, you update the state to reference the left subtree; when you go to the right subtree, the state changes to reference the right subtree, and so on.

Here is an example of how to rewrite the classic insertion into binary tree without recursion:

public TreeNode add(TreeNode node, int value) {
    // Prepare the node that we will eventually insert
    TreeNode insert = new TreeNode();
    insert.data = value;
    // If the parent is null, insert becomes the new parent
    if (node == null) {
        return insert;
    }
    // Use current to traverse the tree to the point of insertion
    TreeNode current = node;
    // Here, current represents the state
    while (true) {
        // The conditional below will move the state to the left node
        // or to the right node, depending on the current state
        if (value < current.data) {
            if (current.left == null) {
                current.left = insert;
                break;
            } else {
                current = current.left;
            }
        } else {
            if (current.right == null) {
                current.right = insert;
                break;
            } else {
                current = current.right;
            }
        }
    }
    // This is the original node, not the current state
    return node;
}

Demo.

Navaneeth Sen · Answer 2 · 2014-11-09T09:22:01.267

Thanks dasblinkenlight..

This is my logic for replacing the above recursive function for a ternary tree.

    Iterator words = treeSearch.getItems().iterator();

    while (words.hasNext())
    {
        for (int i = 0; i < word.getNumberNodeValues(); i++)
        {
            add_Non_Recursive(objectToReference, word, i);
        }
    }

    //Add to Tree
    private void add_Non_Recursive(Object storedObject, ITreeSearch treeSearch, int pos) throws NoSearchValueSetException
    {
        TernaryTreeNode currentNode = rootNode;

        // Start from a node(parentNode). If there is no node, then we create a new node to insert into the tree. 
        // This could even be the root node.
        if (rootNode == null)
        {
            rootNode = new TernaryTreeNode(treeSearch.getNodeValue(pos));
        }
        else
        {
            while (currentNode != null)
            {
                if (currentNode.lessThan(treeSearch, pos))
                {
                    if (currentNode.left == null)
                    {
                        currentNode.left = new TernaryTreeNode(treeSearch.getNodeValue(pos));
                        currentNode = null;
                    }
                    else
                    {
                        currentNode = currentNode.left;
                    }
                }
                else if (currentNode.greaterThan(treeSearch, pos))
                {
                    if (currentNode.right == null)
                    {
                        currentNode.right = new TernaryTreeNode(treeSearch.getNodeValue(pos));
                        currentNode = null;
                    }
                    else
                    {
                        currentNode = currentNode.right;
                    }
                }
                else
                {
                    if (currentNode.mid == null)
                    {
                        currentNode.mid = new TernaryTreeNode(treeSearch.getNodeValue(pos));
                        currentNode = null;
                    }
                    else
                    {
                        currentNode = currentNode.mid;
                    }
                }
            }
        }
    }

But I dropped this logic as it wasnt great in performing, it took more time than the recursive counterpart.

How to convert the below recursive functions to for loop iterations

2 Answers2