Get new post automatically.

Enter your email address:

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 ) {
        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.)