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.