#!/usr/bin/perl

$fibhash{0} = 1;
$fibhash{1} = 1;

sub fib1 { my $n = shift;
	  my $val = $fibhash{$n};
	  if ($val) {$val;} 
	  else
	  {
	    $val = fib1($n-1) + fib1($n-2);
	    $fibhash{$n} = $val;
    	    $val;
	  }
	 }

print (fib1 $ARGV[0]);  #look ma, lambda-calc style application!
print "\n";


#### generic procedure that takes any function and returns a new function
#### that uses the hash table method:

sub makehashfun  
     {
        my $f = shift;
	my $hash;
        sub {
  	      my @args = @_;
	      my $jargs = join ",",@args;
	      my $val = $hash->{$jargs};
	      if ($val) {$val;} 
	      else {
		     $val = $f->(@args);
		     $hash->{$jargs} = $val;
		     $val;
	           }  # else
	    }  # returned sub
     }  # makehashfun


#### test:

#naive, non tail-recursive fib function:

$fib2 = sub { my $n = shift;
              if ($n<2) {1} else {$fib2->($n-1) + $fib2->($n-2)}
	    };

# optimized fib.  note that the same function name should be used:
$fib2 = makehashfun($fib2);

printf $fib2->($ARGV[0]);  print "\n";



#### testing a function with two arguments:
$ff = sub { my $n=shift;  my $m=shift;
	    if ($n==0) {$m;} else {$n+$ff->($n-1,$m-1);}
	  };

print $ff->(7,8);
$ff = makehashfun($ff);

print "\n", $ff->(7,8);  print "\n";

