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.

Lambda is your friend

I've been doing this IT thing for a while now; and I'm about to make a major transition. January 2006 I transitioned from the master ninja Unix sysadmin to the newbie Java developer. It wasn't an easy transition, but I made it. I had a lot of help, mainly from the tech lead on our project, a great guy and excellent developer. But after two and a half years, I'm tired of the Java developer world. It's not so much that I find it hard (it's not), but it's just that it's not where my passion lies. I still have trouble articulating this idea, but I prefer Getting Stuff Done (TM). It's not that I don't respect Java developers (well, I don't respect a lot of them, but that's the nature of anything with huge market share), it's just not a field I find myself passionate about.

So I'm going to a new job soon, returning to the life of Getting Stuff Done (TM). I'm very excited about it.

I think the whole Getting Stuff Done (TM) approach is why I love Perl so much. I use Java at work: it's what I'm paid to do. But when I have a problem that needs to be solved on my own systems, I use Perl. I can solve the problem in Perl in the same time it takes me to write all the boilerplate code in Java.

It's not that Java's bad, it's just that Java isn't good at Getting Stuff Done (TM). I realized in the last 12 months that all Java projects eventually grow into large frameworks. The word "framework" describes Java like "regex" describes Perl or "list" describes Lisp or "pointer" describes C. Java is plagued by thousands of huge frameworks that get stacked on each other, each containing hundreds of classes or interfaces, none actually Getting Stuff Done (TM).

When I tell people I know Java, they want to know which frameworks I use: no one really programs Java, they program collections of frameworks. Our stack involves Hibernate and Spring, so potential employers get excited about that: I guess the Hibernate + Spring stack is a popular one.

Don't get me wrong: I've seen good Java code, and I've written both good and bad Java code; some of it even does the job fairly efficiently. But it's a language that lends itself to Yet Another Framework, rather than a language that lends itself to Getting Stuff Done (TM).

Perl lends itself to Getting Stuff Done (TM).

That's not to say Perl doesn't have its own problems. Much like the Java culture has evolved to produce zillions of frameworks, none of which actually form a complete application; Perl's culture has evolved to produce billions of lines of unreadable code that only the Perl parser has any hope of understanding. And as one friend pointed out: people write bad Perl because they can. So far, the Perl community has been more impressed by obfuscated code than appalled: so Perl newbies learn terrible habits that any other language's community would quickly humiliate them out of.

But Perl's no mean language: it's actually possible to write very elegant and efficient code in Perl; it's just not emphasized by the Perl community like it is in most other communities. Dominus' Higher-Order Perl is a great example of someone looking past "quick and dirty" to "incredible potential". I hope to see many more books like it.

But after writing a lot of code in projects from simple short scripts, to various Java applications, to C plugins, to fairly monstrous Perl and Python programs; I've settled on what I think is my favourite language: Scheme. I've been using Gambit for a while now, and I'm finding it's a very simple, clean, elegant language. But best of all, it's a great language for just getting out of your way and letting you get the job done.

To be sure, I've used a lot of the Gambit extensions, so I'm not at all programming in "pure Scheme"; but the extensions I've been using are also included in most of the Schemes I've seen out there, so I think my code is fairly portable, if not actually standards-compliant.

Gambit also supports hygienic (define-syntax) and non-hygienic (define-macro) macros. That's a huge deal.

But after mucking with Scheme for the past four or five weeks in my spare time; I'm finally seeing the truth in what a lot of old Lispers used to say: the simple syntax (or lack thereof) lets you see the code, not just the syntax. And it's amazing how easy it is to make things happen in Scheme, although it takes a very different mindset from standard Algol derivatives.

Funny thing is, I started trying to learn Lisp maybe five years ago now. But I kept seeing it in little pieces: seeing how cool any one feature is, but never able to combine them all into a working piece of usefulness. But like others have said, with some practice, it suddenly clicked, and I'm writing genuinely working code.

It's all very cool.

I still find Common Lisp a strange entity: it puts all the power in the known universe at your fingertips, but I find it hard to get things done in it. That seems weird when I'm extolling the virtues of Scheme (they are very close cousins, after all); but I still find solutions tend to flow from my fingers in Scheme. In CL I find myself thinking around problems too frequently.

Part of that is CL's insane number of options: accessing a file system in Common Lisp is not a simple task. And that complexity bleeds into my code too. Perhaps my problem is that the Scheme implementations I've tried are better implementations than the CL implementations I've worked with.

But I'm not trying to fan the flames of the infighting between Schemers and Lispers here: I'm just happy to have found a great language to work in.

Some Perl

A buddy of mine sent me a Perl question on AIM. He wanted to count words from STDIN. That is, he wanted to have snippet of Perl that would count the frequency of each word. Presumably he intends to use it in some larger application.

I helped him with his version, then thought about it a little more, realizing I could write something a little shorter, albeit not very efficient. My solution looked something like this:

#!/usr/bin/perl

use strict;

my @words = <>;
chomp @words;
my %count = map {
    my $word = $_;
    $word => scalar grep {$_ eq $word} @words;
} @words;
print "$_ was seen $count{$_} times\n" foreach (sort keys %count);

I was actually kind of proud of that. I know, it's not terribly efficient to have grep inside map, but you gotta admit there's a certain elegance to it...