Example of tail recursive functions for manipulating a singly linked list, inspired by https://plus.google.com/u/0/111049168280159033135/posts/2zMqrkydzJi both gcc -O3 and clang -O3 compile all used recursions to loops therefor the stack does not overflow. Unlike the example linked in the post above this is valid C99 code (no bool, true, false) …

listrec.c

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct node {
	struct node* next;
	int val;
} node;

void prepend(node** l , int val){
	node* new_node;
	new_node  = (node*) malloc(sizeof(node));
	if(new_node == NULL)
	    exit(1);
	new_node->next = *l;
	new_node->val = val;
	*l = new_node;
}

typedef int (* remove_fn)(node* v);

void remove_from_list(node** l, remove_fn r){

	node* entry = *l;
	if (entry == NULL)
		return;
	if (r(entry)){
		*l = entry->next;
		free(entry);
		// Tail recurse into rest of list
		remove_from_list(l, r);
		return;
	}
	remove_from_list(&entry->next, r);
	return;
}

void remove_all(node** l){
	if (*l == NULL)
		return;
	node* entry = *l;
	*l = entry->next;
	free(entry);
	remove_all(l);
}

typedef void (* visit_fn)(node* v);

void visit(node* l, visit_fn v){
	if (l == NULL)
		return;
	v(l);
	visit(l->next, v);
}

int remove_even(node* v){
	if (v->val % 2 == 0){
		return TRUE;
	}
	return FALSE;
}

void print_visit(node* l){
	printf("%d\n", l->val);
}

int main(int argc, char** argv){
	node* list = NULL;
	for (int i = 0; i < 80; i++){
		prepend(&list, i);
	}
	printf("Before remove:\n");
	visit(list, &print_visit);

	remove_from_list(&list, &remove_even);
	printf("After remove:\n");
	visit(list, &print_visit);
	remove_all(&list);
	list = NULL;
	return 0;
}