Recursion without a procedure ("function") in JavaScript

There are several ways to turn a recursive algorithm into an iterative one or at least avoid to do the recursive calls in your own code. In the specific example of yours, where your traverse a tree, some possibilities are:

• You can create a stack data structure explicitly that corresponds to the stack that is otherwise built implicitly by the recursive calls. Whenever in the recursive algorithm you would do a recursive call, you push the current set of variables onto the stack. Then the previous value of the variables is saved on the stack and you can use the variables again as you would within the next recursive call. When in the original algorithm you return from a recursive call, you can restore the values from the top of the stack.
• You can convert the tree into a sequential structure, like a list or an array and then iterate over the array. If the tree comes from a library, it is likely that the library itself offers something like a "tree_to_list" or "tree_to_array" function. But, even if that is not the case, such a conversion from tree to array is simple: You create an array that holds the tree nodes. You initialize the array with with the root node of the tree. Then, in a loop, you iterate over the array indices and for each node you append the children of the node to the arrary (which gets longer while you encounter new nodes with children). This way you will get all the tree nodes into the array without recursion.
• You can use a tree-iterator object that allows you to traverse the tree. The tree-iterator represents a position within the tree. Your algorithm then initializes the iterator to point to the first position of the tree, and, in a loop, operates at the position the iterator represents and afterwards "increments" the iterator. Then, the recursive nature of tree traversal is hidden inside the tree-iterator object (which typically will internally have some stack like structure that is used to implement "incrementing" the iterator). This way, recursion still happens (inside the iterator), but is not apparent from your algorithm.
• If your tree library offers a "map" function for trees this also allows you to keep the recursion off your own code: You define a function that shall be applied to each node in the tree (in your case the function would replace the "a"s), and then call the map function which does the tree traversal for you and will, for each node it finds, call your function for that node.

posted over 2 years ago

CC BY-SA 4.0

2y ago

Dirk Herrmann‭

1387 reputation 1 31 141 48

Yes, it's possible.

In a more general way, every recursive algorithm can be converted to an iterative one (and vice-versa).

You just need to use a stack. Internally, a recursive function will use a stack to "remember" its "level" (because each recursive call is like entering a new "level" - just like dream levels in Inception).

To use an iterative algorithm, you must use the stack yourself. In JavaScript, we can use a simple array for that:

function replaceIn(e) {
    // stack (actually an array) starts with element "e" in it
    var stack = [ e ];

    while (stack.length > 0) {
        // get stack's top
        var currentElement = stack.pop();
        if (currentElement.nodeType == Node.TEXT_NODE) {
            currentElement.nodeValue = currentElement.nodeValue.replaceAll("a", "");
        }
        // add all child nodes to the stack
        for (const child of currentElement.childNodes) {
            stack.push(child);
        }
    }
}

Let's say you call replaceIn(document.body). The stack starts with document.body in it. Then I check if it's a text node and call replace.

After that, I add all child nodes of document.body to the stack. In the next iteration, the stack's top will be one of those nodes. Then I check if it's a text node, replace and add its child nodes to the stack. And so on.

The result will be the same: in the end, all the child nodes, and the grandchild nodes, and grand-grandchild nodes, etc, will be added to the stack. When there are no more child nodes to be added, the loop will finish processing all of them (and remove them from the stack, because that's what pop does), until the stack is empty.

As a side note, for this particular case, I find the recursive algorithm more intuitive, because it's dealing with a hierarchical tree-like structure, which is recursive by definition.

posted over 2 years ago

CC BY-SA 4.0

hkotsubo‭

5110 reputation 20 69 575 228

The typical way to do something like this without involving recursion would be to build an array and iterate through that.

However, in this case, recursion is a more appropriate option. With tree structures like HTML where you don't know ahead of time the depth or breadth of the tree, recursion is usually the easiest way to handle it because it's concise, readable, and efficient. (In terms of time complexity, you're looking at O(n) for recursion vs usually at least O(2n) and worst case O(n^2) or more for loop iteration.)

If you're concerned about stack size, you don't need to be. Most modern browsers have stack limits in the tens of thousands, and you're only adding one stack frame per child level of the HTML tree. If you have a HTML structure that's tens of thousands of levels deep, you have bigger problems!

posted over 2 years ago

CC BY-SA 4.0

ArtOfCode‭ staff

860 reputation 1 19 88 16