Как преобразовать приведенные ниже рекурсивные функции в итерации цикла

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

Это фрагмент моего кода в моем троичном дереве, который я использую для вставки имени человека (может иметь несколько слов в имени, например, Микеле Адамс, Тина Джозеф Джордж и т. Д.). Я хочу преобразовать приведенную выше рекурсию в цикл for / while.

Пожалуйста, объясните мне это.

Answer 1

Общая идея замены рекурсии на итерацию состоит в том, чтобы создать переменную состояния и обновить ее в цикле, следуя тем же правилам, которым вы следуете в своей рекурсивной программе. Это означает, что когда вы выбираете левое поддерево в рекурсивной программе, вы обновляете состояние, ссылаясь на левое поддерево; когда вы переходите к правильному поддереву, состояние изменяется на ссылку на правильное поддерево и т. д.

Вот пример того, как переписать классическую вставку в двоичное дерево без рекурсии:

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.

Answer 2

Спасибо dasblinkenlight..

Это моя логика для замены вышеуказанной рекурсивной функции для троичного дерева.

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

Но я отбросил эту логику, так как она не была великолепна в исполнении, она заняла больше времени, чем рекурсивный аналог.