The Cost of Recursion

By Jon Bentley

Dr. Dobb's Journal June 1998

(a)
void rcount(Tptr p)
{   if (!p) return;
    rcount(p->lo);
    count++;
    rcount(p->hi);  
}
(b)
void rcount2(Tptr p)
{   if (p->lo) rcount2(p->lo);
    count++;
    if (p->hi) rcount2(p->hi);  
}

Example 5: (a) Counting nodes in the tree; (b) reducing number of calls from 2n to n.

Back to Article