Saturday, June 26, 2010

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.

Thursday, June 24, 2010

Poor Navigation

So I'm in Raleigh, NC this week. I head back to the Northwest tomorrow afternoon. Since I'm so close, I lined up lunch with a good friend in Charlotte. It was what they call a "wild hair": a two-to-three hour drive for lunch, but I figured it might be worth it.

I have a pretty sorry little rental car this week, so between my fear of it dying on the Interstate and a desire for a nicer drive, I decided to take 64 to Asheboro, then 49 to Charlotte:

View Larger Map

But I missed the turn from Hwy 1 to Hwy 64 in Apex. I have no idea how I missed it, but I did. I started getting nervous when I saw signs for Southern Pines, but still hadn't seen signs for Siler City.

Yep, I ended up in Moore County, "on the way" to Charlotte. I was south of Sanford.

I had to call both people I meant to meet and tell them. They both laughed, so there were no hard feelings. But I sure felt stupid.

Gah.

Friday, June 18, 2010

Grill pizza stone

In an effort to make the Redneck Pizza Oven a more repeatable experiment, I've been looking for a pizza stone designed for use on the grill. Then Ames bought me this one from Weber as a gift. I gave it a whirl yesterday.

The pies made on the stone bubbled nicely and looked actually rather picturesque:
From Grill Pizza Stone


From Grill Pizza Stone


But when we cut them, we realized the bottoms were charred to almost inedible:
From Grill Pizza Stone


It appears we've been able to get the stone good and hot, but the air above it is too cool. We had this problem last time, and ended up shovelling live coals around the perimeter of the stone to get that temperature up:
From


So it seems we need to make some arrangement like that.


The stone itself appears to be exactly what I was looking for: it handled the heat just fine, although I was half-afraid it would crack. It's marketed specifically for use on a grill, and I read the directions very carefully: I used it exactly in accordance with the directions in the box.

It doesn't look nearly so picturesque now that the stone's been a little charred and the metal's been a little blued, but I have to say it's extremely promising. I think this is going to become a centerpiece of our future pizza explorations.

From Grill Pizza Stone


From Grill Pizza Stone

Thursday, June 17, 2010

Happy Anniversary to us

So Ames and I have been married 15 years today.

Wow.

Saturday, June 5, 2010

NC Bound

I'm heading out to Raleigh, North Carolina June 20--25. It's a business trip: I won't have a ton of time for hobnobbing, but I will absolutely make some time for what friends and family I can reasonably get in touch with.