How to understand the code changing recursion to iteration?

Question

Here is the original link https://stackoverflow.com/a/8512072/1632891. Can somebody help analyze it, or change the c# code to c++ code please.
Suppose you have the following recursive function, which acts like a postorder traversal, and that AbcTreeNode is a 3-ary tree with pointers a, b, c.

public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
        if (x != null) {
            AbcRecursiveTraversal(x.a, list);
            AbcRecursiveTraversal(x.b, list);
            AbcRecursiveTraversal(x.c, list);
            list.Add(x.key);//finally visit root
        }
}

The iterative solution:

int? address = null;
        AbcTreeNode x = null;
        x = root;
        address = A;
        stack.Push(x);
        stack.Push(null)    

        while (stack.Count > 0) {
            bool @return = x == null;

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


            if (@return == true) {
                address = (int?)stack.Pop();
                x = (AbcTreeNode)stack.Pop();
            }


        }

Sorry, what is the question here? Are you asking for translation of someone else's answer on another question to a different programming language? Why not attempt it yourself, and ask a question on a specific issue you encounter along the way, provided you can't resolve it by searching other answers? — CoolBots, Sep 04 '20 at 03:36
oops, I just think it may be a common way to change recursion to iteration for Binary Tree (Inorder Preorder Postorder) Traversal, quick sort and merge sort... — fizzbuzz, Sep 04 '20 at 03:42
It'd probably be worth drawing out some trees and following the recursive version and "see" what it's doing; then write it. — ChiefTwoPencils, Sep 04 '20 at 04:17

score 1 · Answer 1 · answered Sep 04 '20 at 04:00

When a method is called, usually the CPU stack will be used to keep track of the local variables and program counter. When the method returns, the stack and program counter will be restored.

This example replaces every recursive call operation, with a block of code which will perform equivalent steps;

store any local variables stack.Push(x);
remember which block of code to execute on the next "return" stack.Push(C);
set the new argument variables x = x.b;
jump to the beginning of the method address = A; break;
the point to resume execution case C:

The "return" operation is then replaced with a block of code that either restores local variables & jumps to the most recent return location, or exits the function.

If I were writing an example, I would have restored local variables after each case label, instead of in a common return block. Because you only need to store variables that are "live" at each call/return site. — Jeremy Lakeman, Sep 04 '20 at 04:04

How to understand the code changing recursion to iteration?

1 Answers1