ezyang’s blog

the arc of software bends towards understanding

Tail recursion makes your loops cleaner

Recursion is one of those things that functional programming languages shine at—but it seems a bit disappointing that in many cases, you have to convert your beautiful recursive function back into iterative form. After all, iteration is what imperative languages do best, right?

Actually, explicitly tail-recursive functions in functional programming languages can be fairly beautiful: in fact, in the cases of complicated loops, they can be even prettier than their imperative counterparts. Take this midpoint line-drawing algorithm as an example:

circleMidpoint d r = go 0 (-r) k0
    where k0 = 5 - 4 * r
          x1 = ceiling (fromIntegral r / sqrt 2)
          go x y k | x > x1    = return ()
                   | k > 0     = d (x,y) >> go (x+1) (y+1) (k+8*x+8*y+20)
                   | otherwise = d (x,y) >> go (x+1)  y    (k+8*x+12)

There are three loop variables: x, y and k, and depending on various conditions, some of them get updated in different ways. x is a bog-standard loop variable; ye old C-style for loop could handle it just fine. But y and k are updated differently depending on some loop conditions. But since they’re parameters to the go helper function, it’s always clear what the frequently changing variables are. You lose that nice structure in the imperative translation:

// global variables and loop variables are all mixed together
int k = 5 - 4 * r;
int y = -r;
int x1 = ceil(r/sqrt(2));
for (int x = 0; x <= x1; x++) { // only x is obviously an index var
  draw(x, y);
  if (k > 0) {
    k += 8*x + 8*y + 20;
  } else {
    k += 8*x + 12;
  // does it ever make sense for any code to live here?

I’ve also managed to introduce a bug in the process...

9 Responses to “Tail recursion makes your loops cleaner”

  1. Dan Doel says:

    To be fair…

    int x1 = ceil(r/sqrt(2));

    for(int x = 0, int k = 5 – 4*r, int y = -r ; x < x1 ; x++) { …

    is an option (assuming I haven't messed up the syntax).

  2. Yes, that’s true. Though, you still fail to update the “loop variables” in the third segment (you could probably hack it in there too, but then the code is getting a bit dodgy…)

  3. MarkusQ says:

    :) Two bugs, actually (assuming the haskell version is canonical).

    — MarkusQ

  4. Oh yes, that second bug was inadvertent, I’ve (hopefully) fixed it now.

  5. MarkusQ says:

    Yep. :)

    Nice post, BTW.

    — MarkusQ

  6. Anonymous says:

    for (int x = 0, int k = 5 – 4*r, int y = -r;
    x 0?(++y,8*y+20):12), ++x)
    draw(x, y);

  7. Anonymous says:

    for (int x = 0, int k = 5 – 4*r, int y = -r;
    x <= ceil(4/sqrt(2));
    k += 8*x + (k>0?(++y,8*y+20):12), ++x)
    draw(x, y);

  8. augustss says:

    A pity you didn’t use a tail recursive function to illustrate tail recursion.

  9. re: augustss says:

    Truth is beauty; beauty, truth*.

    * Except in lame “go functional programming!” posts.

Leave a Comment