Considering Recursion 
by Arch D. Robison

Listing One
//-----------------------------------
// Non-recursive version.
//-----------------------------------
   ....
   for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            a[i][j] += b[i]*c[j];
   ....
//-----------------------------------
// Recursive #1 (classical tail call)
//-----------------------------------
void inner1 (int i, int j, int n) {  // Forced to name inner loop
    if (j<n) {
        a[i][j] += b[i]*c[j];
        inner1(i,j+1,n);
    }
}
void outer1 (int i, int n ) {        // Forced to name outer loop
    if (i<n) {
        inner1(i,0,n);
        outer1(i+1,n);
    }
}
    ...
    outer1(0,n);                     // Need ``root'' call.
//-----------------------------------
// Recursive #2 (typical backwards order)
//-----------------------------------
void inner2 (int i, int j, int n) {
    if (j>0) {
        --j;
        inner2(i,j,n);
        a[i][j] += b[i]*c[j];
    }
}
void outer2 (int i, int n) {
    if (i>0) {
        --i;
        inner2(i,n,n);
        outer2(i,n);
    }
}
    ...
    outer2(n,n);


Listing Two
struct node {
    node* left;    // Points to left child.
    node* right;   // Points to right child.
    ...data...
};
//-----------------------------------
// Obvious recursion
//-----------------------------------
void walk (node* p) {
    if (p) {
        ...process node *p...
        walk(p->left);
        walk(p->right);
    }
}
//-----------------------------------
// Faster - mixes recursion and iteration
//-----------------------------------
void walk (node* p) {
    while(p) {
        ...process node *p...
        if (p->left) {
            if (p->right) {
                walk(p->left);       // General case - recurse to left
                p=p->right;  // and iterate to right.
            } else p=p->left; // Special case. iterate to left if 
                              //     there is no right subtree
        } else p=p->right;   // Special case. iterate to right if 
                             //      there is no left subtree
    }
}

Listing Three
//----------------------------
// Unoptimized obvious recursion
//----------------------------
void walk_backward( node * p ) {
    if (p) {
        walk_backward(p->next);
        ...process node *p...
    }
}
//----------------------------
// Iterative version
//----------------------------
void walk_backward (node* p) {
    // Pass 1: determine size of array.
    size_t n=0;
    for (node* q=p; q; q=q->next )
        ++n;
    // Pass 2: fill the array.
    node** array = new node*[n];
    size_t k=0;
    for (node* q=p; q; q=q->next)
        array[k++] = q;
    // Pass 3: traverse the array backwards.
    while (k>0)
        process (array[--k]);
    delete[] array;
}

Listing Four
// Uses type  node from Listing Two
void tree_visitor (node* root, void (*f)(node&)) {
    while (root) {
        // Recurse to left.
        tree_visitor (root->left, f);
        (*f)(*root);
        // Iterate to right.
        root = root->right;
    }
}
void walk_tree (node* root) {
    tree_visitor(root, process_node);
}

Listing Five
// Uses type node from Listing Two
class tree_iterator {
public:
    tree_iterator( node* n ) : sp(stack) {
        if (n) {
            // Mark down to leftmost node, pushing skipped nodes on stack.
            for (; node* m = n->left; n=m) *sp++ = n;
        }
        at = n;
    }
    node& operator*() const {return *at;} // Return reference to current node
    bool is_end() const {return at==NULL;} // Return true if past last node
    void operator++() {
        if (sp==stack) {
            // No more pending nodes.
            at = NULL;
        } else {
            // Pop pending node from stack.
            at = *--sp;
            // March down to leftmost node, pushing skipped nodes on stack.
            for (node* n = at->right; n; n=n->left) *sp++ = n;
        }
    }
private:
    static const int STACK_MAX=32; // Limit on depth of tree.
    node* at;                  // Points to current node, or NULL if at end.
    node** sp;                 // Points to top of stack.
    node* stack[STACK_MAX];    // Stack of pending nodes.
};
void walk_tree( node* n ) {
    for (tree_iterator i(n); !i.is_end(); ++i)
         process_node(*i);
}

Listing Six
// Uses type node similar to that in Listing Two, but with added parent link.
struct node {
    node* left;    // Points to left child.
    node* right;   // Points to right child.
    node* parent;  // Points to parent.  NULL if root.
    ...data...
};
class tree_iterator {
public:
    tree_iterator( node* n ) {
        if (n) {
            // Jump to leftmost node of subtree rooted at n.
            while (node* m = n->left) n=m;
        }
        at = n;
    }
    node& operator*() const {return *at;} // Return reference to current node.
    bool is_end() const {return at==NULL;} // Return true if past last node.
    void operator++() {
        node* m = at;
        node* n=m->right;
        if (n) {
            // Jump to leftmost node of subtree rooted at n.
            while ((m=n->left)!=NULL) n=m;
        } else {
            // March up tree until we much up left link.
            while ((n=m->parent)!=NULL && n->right==m)  m=n;
        }
        at = n;
    }
private:
    node* at;     // Pointer to current node, or NULL if at end.
};
void walk_tree (node* n) {
    for (tree_iterator i(n); !i.is_end(); ++i)
        process_node(*i);
}



6


