Tail Recursion Is Its Own Reward: Wait, What is Tail Recursion?
Is it weird that I read about functional programming to relax at night? Don’t answer that. I’ve been fascinated with tail recursion for a while and a few weeks ago I gave a lightning talk about what it is.
It can be a confusing concept. From my research, there are three conditions necessary for tail recursion:
- a tail call
- a linear iterative process
- an interpreter that can run a linear iterative process executed using recursion that does not use the call stack
This leads to a process that evolves in constant space. Which is epic.
A Tail Call
A tail call’s official definition is “a subroutine call that is performed as the final action of a procedure.” Naturally, we’ll be looking at this in Scheme LISP.
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
The tail call is just that function call at the end of the procedure (factorial (- n 1)
A Linear Recursive Process: Not Tail Recursive
The procedure we just defined, while it does have a tail call, is not tail recursive. Working from 1.2.1 of SICP, we can see that this procedure generates a linear recursive process, which looks like this:
The key point here is that the evaluation of the procedure is delayed until the stopping condition (= n 1) is met. It creates a chain of deferred operations and the interpreter has to keep track of all these operations. This takes up an amount of memory and requires a number of steps that grows linearly with n.
Linear Iterative Process: It’s Tail Recursive!
There is another way to write the factorial function, using an iterative approach:
(def (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
This procedure generates a process that looks like this:
Even more exciting, it executes in constant space! The process does not grow or shrink. It is characterized by updating the value of a set of state variables at each iteration.
One way to think about it is that the process could be stopped at any point and then restarted. There are no deferred operations.
Can your interpreter tail recurse?
Only some languages have interpreters that enable tail recursion.
These interpreters execute a linear iterative process without needing to store the state variables on the call stack.
They can update the values only on the machine “registers.” The benefit? No possibility of a stack overflow!
Here’s showing the contrast in the shape of the process generated by the procedure.
You might say, but wait, isn’t this what a for loop does? Yes, in the way that a for loop enables us to create a procedure that executes in constant space. But non-tail recursive languages have to rely on special constructs to make this happen.
For loops also tend to encourage imperative style programming…
Wait, but why do I care?
One of the main reasons to care is that we can write functions that execute in constant space. But, given that this can be accomplished with for loops why does it matter?
Tail recursion enables a functional style of programming.
SICP 3.1.3 provides us with a great example between an imperative and functional programming style. Compare these two procedures:
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
This implementation of factorial uses a functional style. The big distinction is that it passes the updated values as arguments in the internal iterative loop generated by a recursive procedure.
A big breakthrough for me for understanding functional programming was the realization that the names here are not variable assignment but rather the names given to arguments then passed as modified arguments to the recursive tail call. Beautiful!
(define (factorial n)
(let ((product 1)
(counter 1))
(define (iter)
(if (> counter n)
product
(begin (set! product (* counter product))
(set! counter (+ counter 1))
(iter))))
(iter)))
Whereas this procedure assigns a value to a variable and then reassigns the variable at each iteration of the loop.
Hal and Gerry point out that this creates the possibility for a subtle bug: if you change the order of these lines, the procedure returns the wrong result, since the counter would be updated before calculating the new product.
(begin (set! product (* counter product))
(set! counter (+ counter 1))
They say that this forces programmers to pay careful attention to the order of assignment, which isn’t an issue with functional programming. They also point out that this continual updating of assignment creates serious issues when managing concurrent processes.
This style also makes it possible to use immutable data, something impossible with imperative programming’s need to use assignment.
Tail recursion! So cool. For me, exploring this concept shined insight into the heart of what functional programming is.