Why tail-recursive functions are loops

Summary

One story every computing enthusiast should hear is the lesson of how loops and tail-recursion are equivalent. We like recursive functions because they’re amenable to induction, and we can derive them in a way that is in direct correspondence with the definition of the datatype over which they recur. We like loops because they’re fast and make intuitive sense as long as variables don’t change in too tricky a way. In general, recursive functions are slower than loops because they push stack frames: the performance of most programs today is dominated by memory reads/writes. The data we touch the most lives in the cache–we do not want to evict a ton of stuff from the cache, under any circumstance. In a direct-style implementation of a recursive function, the recursive call has to push a stack frame to remember what to do once the function returns: ;; Racket (define (sum l) (if (empty? l) 0 (+ (first l) (sum (rest l))))) // C int sum(int *l, int length) { if (length == 0) return 0; else return l[0] + sum(l + 1, length - 1); } When we get to (+ (first l) (sum (rest l))), we first call (first l) (which returns the first element). While we’re making that call, we have to remember to come back and do (sum (rest l))–to be fully precise, we remember that we need to do (rest l), then take its result x and call (sum x), remembering to come back and finally take that result and add it to the result of (first l). The reason we have to do this is because we need to remember those partial results (in this case the result of (first l)): we have to store them somewhere after all, and each time we make the recursive call, we need to remember the result of (first l) from this call–we need O(n) stack space for a list of size n. Of course, if we use iteration this all goes away: ;; Racket (define (sum l) (define x 0) (for ([elt l]) (set! x (+ x elt))) x) // C int sum(const int *l, int length) { int x = 0; for (int i = 0; i < length; i++) { x += l[i]; } return x; } We all have an intuitiv...