void addToEnd(const int x, List& L) { if(L == NULL) { L = cons(x, NULL); } else { addToEnd(x, L->tail); } }
Since the definition of addToEnd is tail-recursive, an optimizing compiler can turn it into a loop.
void addToEnd(const int x, List& L) { List& p = L; while(!isEmpty(p)) { p = p->tail; } p->tail = cons(x, emptyList); }
When the loop ends, p is a variable that holds NULL. It is the 'tail' variable in the last cell, or is variable L if L is NULL. It is important to use p->tail instead of tail(p) since tail(p) is not a variable.