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.

The One True Cross

I've been playing with Scheme, and have (almost reluctantly) concluded that Gambit Scheme might be the One True Cross.

If you've not played with Scheme, it's a reasonably minimalist Lisp dialect characterized by a single namespace (functions and variables share single namespace) and lexical scope (variables are bound as they are defined, rather than as they are called). Scheme is Lisp, with all the complexity and magic that implies.

I started playing with Scheme a little when reading The Little Schemer this last spring; but I wasn't in love with it enough to actually try using it. But in the last three weeks, I have suddenly found myself playing more and more... and actually getting useful code written!

I've been using Gambit, which is a Scheme renowned for its abilities in massive concurrency and parallelization. In English, Gambit is very good at allowing a programmer to spawn a number of autonomous computations that occur more or less simultaneously. So instead of doing A, then B, then C; Gambit lets you do A & B & C, all at once.

But Gambit's real strengths for me lay in three lesser-touted features:

1. Gambit has simple and powerful hooks into the host operating system. This is a major deal after trying for ages to get something close to usable out of Common Lisp for day-to-day hack scripts. See, in the end my life is rather dull: I don't need to encrypt huge amounts of data or write a new programming language nearly as frequently as I need to back up files or directories on my laptop. Common Lisp makes it easy to do the former, not so easy to do the latter. But Gambit steps in with some simple functions like file-exists? or directory-files to test for file existence or find directory contents, respectively. It was very simple to write Scheme equivalents to the Perl commands I use the most (-x, -d, etc.) and suddenly Gambit was teaming with admin scripting potential!


2. Gambit has a script mode. So instead of starting up a REPL, loading some files, and throwing off complex-looking commands; Gambit lets me start a file with something like #!/usr/bin/gsi-script and get stuff done.


3. Gambit can compile Scheme code to C, thence to native binaries. This is a major win, because it means I can write something in Scheme, compile it and distribute it as native code, and the end user has no idea what language it was written in. Best of all, a script can be run via gsi-script until it seems stable, then it can be compiled to C and thence to binary without further ado. They can be tested as scripts, and compiled when they pass testing.

One more thing, Gambit's fast: recursive directory tree walks are like lightning. I've been using a simple backup program I wrote in Gambit, and it zooms through copying my data.

But I'm starting to figure out what others have hinted at: Lisp (and Scheme) is more of a phenomenon than a programming language. You don't just learn Scheme; you explore it. And as you explore it, you start to slowly see the depths of potential that your computer doesn't know it has. Scheme becomes a road to enlightenment, not a language to make computers do stuff.