The Cost of Recursion

By Jon Bentley

Dr. Dobb's Journal June 1998

(a)
void rcount3(Tptr p)
{   while (p) {
        if (p->lo) rcount3(p->lo);
        count++;
        p = p->hi;
    }
}
(b)
void icount(Tptr p)
{   Tptr s[MAXN];
    int sp = 0;
    for (;;) {
        while (p) {
            s[sp++] = p;
            p = p->lo;
        }
        if (sp == 0) break;
        p = s[--sp];
        count++;
        p = p->hi;
    }
}

Example 6: (a) Final call in rcount3 is tail recursive; (b) resulting icount function uses its own stack.

Back to Article