Binary Tree: Data Structures and Algorithms

Recursively Defined Lists

We can define a list as:

1. empty or
2. containing a node and a link to a list.

A list can be scanned using a recursive function: eg. to count the number of items in a list:

int ListCount( List l ) {
    if ( l == NULL ) return 0;
    else return 1 + ListCount( l->next );
    }

However, it turns out to be much faster to write this function without the recursive call:

int ListCount( List l ) {
    int cnt = 0;
    while ( l != NULL ) {
        cnt++;
        l = l->next;
        }
    return cnt;
    }

The overhead of calling a function is quite large on any machine, so that the second iterative version executes faster. (Another factor is that modern machines rely heavily on the cache for performance: the iterative code of the second version doesn't use so much memory for the call stack and so makes much better use of the cache.)