Tail Recursion

There was a conversation at work a few weeks back on the difference between recursion and iteration. Someone made the claim "Recursion doesn't always work," and pointed out that the Fibonacci Sequence, while easy to implement in naive recursion, tends to blow up when the numbers get large.

I argued that there is an efficient solution using tail-recursion. It's faster than naive recursion, and simpler than an iterative solution.

A third person pointed out tail-recursion is a Scheme thing, and not all languages properly optimize it. This is completely true, but... it's also true that tail-recursive algorithms are in principle more efficient. Abelson and Sussman point out that doesn't always translate into actual performance, though:

most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while.

So here's a short test... I wrote a short tail-recursive Fib generator in Common Lisp. Note it takes a number (i.e. the number of terms to generate) and returns a list representing the sequence:

(defun fibonacci-sequence (num)
  "Calculate a Fibonacci sequence to a number NUM."
  (labels ((fib (n acc)
      (cond ((equalp n 0) acc)
     (T (fib (1- n)      
      (cons (+ (car acc)
        (cadr acc)) acc))))))
    (cond ((= num 0) '(1))
   ((= num 1) '(1 1))
   ((> 0 num) 'undefined)
   (T (reverse (fib (- num 2) '(1 1)))))))

We can loosely translate that to Perl. Perl doesn't have an equivalent to Common Lisp's 'labels', so I had to write two named functions to implement it. But this short script is more-or-less equivalent to the Lisp version: it takes a number on the command line and prints a list representing a sequence with that number of terms:

#!/usr/bin/perl

=head1 NAME

  fib-sequence.pl

=head1 AUTHOR

Clumsy Ox

=head1 SYNOPSIS

  fib-sequence.pl $NUMBER

=head1 DESCRIPTION

Calculates the Fibonacci Sequence to $NUMBER terms.

This is just an exercise in tail-recursion.

=cut

use strict;
use warnings;

use Data::Dumper;

my $number = shift;

my @sequence = fibonacci ($number);

print STDOUT join (', ', @sequence), "\n";

=head2 fibonacci

  fibonacci ($number) => @sequence
  
=cut
sub fibonacci {
  my $num = shift;

  return (1) if $num == 0;
  return (1, 1) if $num == 1;

  return reverse fibt( $num - 2, 1, 1);
} 

=head2 fibt

   fibt ($number) => @sequence

=cut
sub fibt {
  my $num = shift;
  return @_ if $num == 0;
  return fibt ( $num - 1, $_[0] + $_[1], @_);
}

Notice both solutions accumulate the sequence as a list. So there is some definite overhead in carrying that sort of data structure, but it's "fair" in the sense that both are having to do it.

Just informally checking it, the Perl solution is slower than the Lisp solution, but not by an amazing amount. I ran a quick-n-dirty test of the Perl solution, and it timed out reasonably. But I found it blew Perl's number stack very quickly and went to 'inf':

bash-3.2$ time ./fib-sequence.pl 10000 > /tmp/output
Deep recursion on subroutine "main::fibt" at ./fib-sequence.pl line 56.

real    0m1.072s
user    0m0.640s
sys     0m0.380s

Just for comparison, Lisp returned:

(time (fib-sequence 10000))
Evaluation took:
  0.019 seconds of real time
  0.018860 seconds of total run time (0.012529 user, 0.006331 system)
  [ Run times consist of 0.010 seconds GC time, and 0.009 seconds non-GC time. ]
  100.00% CPU
  47,236,537 processor cycles
  4,893,824 bytes consed

Both took longer to print the result than to actually calculate it.

I haven't tried the experiment in Java or C, but I think it might be interesting to see what would happen.


Incidentally, according to SBCL, the 10,000th element of the Fibonacci Sequence is a 2090 digit number:

(format t "~:d" (car (last (fib-sequence 10000))))
33,644,764,876,431,783,266,621,612,005,107,543,310,302,148,460,680,063,906,564,769,974,680,081,442,166,662,368,155,595,513,633,734,025,582,065,332,680,836,159,373,734,790,483,865,268,263,040,892,463,056,431,887,354,544,369,559,827,491,606,602,099,884,183,933,864,652,731,300,088,830,269,235,673,613,135,117,579,297,437,854,413,752,130,520,504,347,701,602,264,758,318,906,527,890,855,154,366,159,582,987,279,682,987,510,631,200,575,428,783,453,215,515,103,870,818,298,969,791,613,127,856,265,033,195,487,140,214,287,532,698,187,962,046,936,097,879,900,350,962,302,291,026,368,131,493,195,275,630,227,837,628,441,540,360,584,402,572,114,334,961,180,023,091,208,287,046,088,923,962,328,835,461,505,776,583,271,252,546,093,591,128,203,925,285,393,434,620,904,245,248,929,403,901,706,233,888,991,085,841,065,183,173,360,437,470,737,908,552,631,764,325,733,993,712,871,937,587,746,897,479,926,305,837,065,742,830,161,637,408,969,178,426,378,624,212,835,258,112,820,516,370,298,089,332,099,905,707,920,064,367,426,202,389,783,111,470,054,074,998,459,250,360,633,560,933,883,831,923,386,783,056,136,435,351,892,133,279,732,908,133,732,642,652,633,989,763,922,723,407,882,928,177,953,580,570,993,691,049,175,470,808,931,841,056,146,322,338,217,465,637,321,248,226,383,092,103,297,701,648,054,726,243,842,374,862,411,453,093,812,206,564,914,032,751,086,643,394,517,512,161,526,545,361,333,111,314,042,436,854,805,106,765,843,493,523,836,959,653,428,071,768,775,328,348,234,345,557,366,719,731,392,746,273,629,108,210,679,280,784,718,035,329,131,176,778,924,659,089,938,635,459,327,894,523,777,674,406,192,240,337,638,674,004,021,330,343,297,496,902,028,328,145,933,418,826,817,683,893,072,003,634,795,623,117,103,101,291,953,169,794,607,632,737,589,253,530,772,552,375,943,788,434,504,067,715,555,779,056,450,443,016,640,119,462,580,972,216,729,758,615,026,968,443,146,952,034,614,932,291,105,970,676,243,268,515,992,834,709,891,284,706,740,862,008,587,135,016,260,312,071,903,172,086,094,081,298,321,581,077,282,076,353,186,624,611,278,245,537,208,532,365,305,775,956,430,072,517,744,315,051,539,600,905,168,603,220,349,163,222,640,885,248,852,433,158,051,534,849,622,434,848,299,380,905,070,483,482,449,327,453,732,624,567,755,879,089,187,190,803,662,058,009,594,743,150,052,402,532,709,746,995,318,770,724,376,825,907,419,939,632,265,984,147,498,193,609,285,223,945,039,707,165,443,156,421,328,157,688,908,058,783,183,404,917,434,556,270,520,223,564,846,495,196,112,460,268,313,970,975,069,382,648,706,613,264,507,665,074,611,512,677,522,748,621,598,642,530,711,298,441,182,622,661,057,163,515,069,260,029,861,704,945,425,047,491,378,115,154,139,941,550,671,256,271,197,133,252,763,631,939,606,902,895,650,288,268,608,362,241,082,050,562,430,701,794,976,171,121,233,066,073,310,059,947,366,875

Update: I decided to try a quick-n-dirty Java implementation. It's rough and ugly, but it seems to work.

Here's where it gets interesting: the Java solution works just fine, but it's slow, and it runs into a StackOverflow at just over 10,000 elements. I suspect that could be increased dramatically with some better java runtime settings, but it seems to disprove my thesis that tail recursion is an appropriate solution regardless of implementation language.

I was also able to get Perl to give me better results with

use bignum;

Still, Lisp is by far the fasest solution.

Lying for Mother Earth

For various reasons, I ride the bus and/or my bike to work most of the time. The idea is actually to phase out the bus and ride just my bike sometime this spring, but it's still a little cool and wet for that just now.

The university where I work is part of a county-wide campaign to reduce single-passenger cars on the roads (largely in the name of going green), and so we're all encouraged to log our trips to/from work with Pierce Trips Commute Calendar, apparently a county-run logger to track one's travels in non-single-driver commutes. This calendar makes some calculations of how much gas, money, and emissions you save over 'if you had driven alone.' There are incentives and prizes given out, both by the school and the county based on people's participation in the program. HR encourages the use of the calendar, which is fine by me.

I started using the calendar sometime in November.

You can actually see their calculations on a "Results" page, so every once in a while I take a look. I'm always struck by the patent dishonesty of their calculations. Here are my results as of today:

You've entered 32 trips since November 19, 2008
You eliminated 659.2 drive-alone miles.

You prevented the following from being emitted into the environment*:
535.78 pounds of carbon dioxide (contributes to global warming)
1.97 pounds of hydrocarbons (contributes to smog)
18 pounds of carbon monoxide (poisonous gas)

You saved 27.49 gallons of gasoline and $116.83 dollars*.

*Statistics based on average emissions for passenger cars and average gas price of $4.25.

So let's examine these numbers.

1. Not every trip has been correctly entered, as I occasionally forget to do so until after I have forgotten details. So I probably actually saved a good deal more. But that's not the calendar's fault.


2. The mileage is correct, according to Google Maps. Actually, my bike rides are longer than my bus and car rides (the direct route is not safe on a bike), but I log them as the same distance, because it's how many miles I saved, not how many I rode. So I've "saved" 659.2 miles.


3. They calculate I've saved $116.83 dollars (sic). Let's ignore the redundancy for now, and examine this number. It's "based on... average gas price of $4.25". Gas hasn't cost $4.25/gallon since long before November 2008. It hung around $1.70/gallon for several weeks, and is now somewhere less than $2.50/gallon. So they're basing the calculation on some fantasy gas price.


4. The "savings" in gas are based on $4.25/gal * 27.49 gal = $116.83. My calculator agrees with them, although as we've already seen, the actual average gas price is about half the number they calculate. But let's not be hasty: bus fare is $1.75/trip. So those 32 trips theoretically cost me 32 * $1.75 = $56.00. So when I subtract my bus fare, I actually "saved" only $60.83. Hmmm... not such a great savings. And if we correct for a more realistic gas price, it looks like I actually only came out ahead about $12.73.


5. I have a bus pass, which lists at $63 / month. That's cheaper than paying regular fare, but it still means I paid (theoritically) $189 for November--January. So I'm actually coming out $72.17 behind for those three months.


6. The $12.73 I saved (correcting for bus fare) aren't that impressive, given my commute time is about 25 minutes one-way in my car to work. But the bus trip takes me about 1:15 hours, so I take about 50 minutes longer one way to get to work. On 32 trips, that's 1600 minutes, or 27:40 hours. So I saved $12.73 in exchange for 27:40 hours. That means my time is valued at about $0.50/hr.


7. I notice the emissions calculation also ignores the emissions the city bus makes in taking me to work, which entails at least one stop and subsequent restart specifically for me each way. The bus burns a great deal more fuel than my car, and emits a great deal more nasty stuff too. I don't have any real numbers for that, but I suspect it's at least 10-25% lower than they glowingly report, once it's amortized across all the bus riders (I've frequently been one of three passengers on a bus).

So they're pretty much lying to me about my "achievement".

The situation's not quite so dim as they raw numbers indicate. I get a serious discount on a monthly bus pass as a perk of working on campus, so I pay much less than $1.75 fare. And my car's a Suburban, so I burn more gas than they think. And honestly, I've used pretty rough numbers here. Not all my "saving" rides are on the bus: some are on my bike, which has no fare. And neither the calendar nor I have amortized vehicle maintenance over those trips. Of course, we'd need to amortize bike maintenance costs too.

But the point is, they don't actually know that. This is not my employer's project, it's a county project: not everyone on it gets discounted bus passes, not everyone drives an enormous beast when they do drive. And the gas price "estimates" are blatantly dishonest.

I intend to continue to ride my bike and/or the bus to work for reasons of my own. Not because of global warming (anthropogenic global warming is a political myth), but for reasons like a general disapproval of wastefulness and the fact that every mile I bike is a little less Ox.

But I thought it interesting how disingenuous this particular [county] government project is.