Why is it that whenever recursion comes up, someone invariably gives a terrible fibonacci implementation?

A much more practical example would be directory traversal in a filesystem. Take a quick look at the opendir and readdir functions, and try making a program that finds all the files in a directory and all subdirectories.

Here's a bit of code to get you started:

#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>

int isdirectory(char *f) {
    struct stat s;
    return stat(f,&s) == -1 ? 0 : S_ISDIR(s.st_mode);
}

and for reading the directories themselves,

DIR *d;
struct dirent *e;
char *dirname;
d = opendir(dirname);
while ((e = readdir(d))) {
    // do stuff with e->d_name here
}
closedir(d);