Data Structures and Algorithms

Recursively Defined Lists

We can define a list as:

empty or
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.)

Back to trees
Table of Contents