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

https://bloggingisaresponsibility.wordpress.com/2012/05/09/tail-recursion-functional-programmings-shame/

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

end

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?

### Like this:

Like Loading...

*Related*