Tail Recursion: Another Look

Previously I criticized tail recursion as the worst kind of memory management. You can read that article here:

But this is not the end of the story.

First, my claim that tail recursion was the WORST kind of memory management was overblown. Although architectural changes are required for tail recursion, manual memory management could require global tracking that would lead to even greater code changes. This is academic at this point because modern imperative languages do not require memory management.

Second, tail recursion may have benefits. Take a generic looping pattern:

n = 5
result = 0
while n > 0
result = result + n
n = n – 1
return n

A regular recursive example would be:

sum n → if n > 0 then n + sum (n-1) else 0
sum 5

While a tail recursive example would be:

sum n → sum’ n 0 where
sum’ n result → if n > 0 then sum’ (n-1) (result+n) else result
sum 5

A bit longer, but it’s more straight-forward, especially if we consider the local definition to be a loop. It’s also more amenable to multiple results and (contrary to the implication of my previous post) more intuitive. With optional variable values, we can even eliminate the need for a local definition:

sum n (result:0) → if n > 0 then sum (n-1) (result+n) else result
sum 5

What’s more, since the recursive call can be considered a manual loop invocation with explicit transformations on its conditions and outputs, it maps more cleanly onto the concept of loop variants and invariants. In short, this may be a more sound practice with value beyond memory management.

With that said, is the ability to map from an imperative loop to a recursive function an advantage? Aren’t we just encouraging imperative thinking? Shouldn’t we encourage functional thinking all the way down?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s