t/op/recurse.t

   1 #!./perl
   2
   3 #
   4 # test recursive functions.
   5 #
   6
   7 print "1..25\n";
   8
   9 sub gcd ($$) {
  10     return gcd($_[0] - $_[1], $_[1]) if ($_[0] > $_[1]);
  11     return gcd($_[0], $_[1] - $_[0]) if ($_[0] < $_[1]);
  12     $_[0];
  13 }
  14
  15 sub factorial ($) {
  16     $_[0] < 2 ? 1 : $_[0] * factorial($_[0] - 1);
  17 }
  18
  19 sub fibonacci ($) {
  20     $_[0] < 2 ? 1 : fibonacci($_[0] - 2) + fibonacci($_[0] - 1);
  21 }
  22
  23 # Highly recursive, highly aggressive.
  24 # Kids, don't try this at home.
  25 #
  26 # For example ackermann(4,1) will take quite a long time.
  27 # It will simply eat away your memory. Trust me.
  28
  29 sub ackermann ($$) {
  30     return $_[1] + 1               if ($_[0] == 0);
  31     return ackermann($_[0] - 1, 1) if ($_[1] == 0);
  32     ackermann($_[0] - 1, ackermann($_[0], $_[1] - 1));
  33 }
  34
  35 # Highly recursive, highly boring.
  36
  37 sub takeuchi ($$$) {
  38     $_[1] < $_[0] ?
  39         takeuchi(takeuchi($_[0] - 1, $_[1], $_[2]),
  40                  takeuchi($_[1] - 1, $_[2], $_[0]),
  41                  takeuchi($_[2] - 1, $_[0], $_[1]))
  42             : $_[2];
  43 }
  44
  45 print 'not ' unless (($d = gcd(1147, 1271)) == 31);
  46 print "ok 1\n";
  47 print "# gcd(1147, 1271) = $d\n";
  48
  49 print 'not ' unless (($d = gcd(1908, 2016)) == 36);
  50 print "ok 2\n";
  51 print "# gcd(1908, 2016) = $d\n";
  52
  53 print 'not ' unless (($f = factorial(10)) == 3628800);
  54 print "ok 3\n";
  55 print "# factorial(10) = $f\n";
  56
  57 print 'not ' unless (($f = factorial(factorial(3))) == 720);
  58 print "ok 4\n";
  59 print "# factorial(factorial(3)) = $f\n";
  60
  61 print 'not ' unless (($f = fibonacci(10)) == 89);
  62 print "ok 5\n";
  63 print "# fibonacci(10) = $f\n";
  64
  65 print 'not ' unless (($f = fibonacci(fibonacci(7))) == 17711);
  66 print "ok 6\n";
  67 print "# fibonacci(fibonacci(7)) = $f\n";
  68
  69 $i = 7;
  70
  71 @ack = qw(1 2 3 4 2 3 4 5 3 5 7 9 5 13 29 61);
  72
  73 for $x (0..3) {
  74     for $y (0..3) {
  75         $a = ackermann($x, $y);
  76         print 'not ' unless ($a == shift(@ack));
  77         print "ok ", $i++, "\n";
  78         print "# ackermann($x, $y) = $a\n";
  79     }
  80 }
  81
  82 ($x, $y, $z) = (18, 12, 6);
  83
  84 print 'not ' unless (($t = takeuchi($x, $y, $z)) == $z + 1);
  85 print "ok ", $i++, "\n";
  86 print "# takeuchi($x, $y, $z) = $t\n";
  87
  88 {
  89     sub get_first1 {
  90         get_list1(@_)->[0];
  91     }
  92
  93     sub get_list1 {
  94         return [24] unless $_[0];
  95         my $u = get_first1(0);
  96         [$u];
  97     }
  98     my $x = get_first1(1);
  99     print "ok $x\n";
 100 }
 101
 102 {
 103     sub get_first2 {
 104         return get_list2(@_)->[0];
 105     }
 106
 107     sub get_list2 {
 108         return [25] unless $_[0];
 109         my $u = get_first2(0);
 110         return [$u];
 111     }
 112     my $x = get_first2(1);
 113     print "ok $x\n";
 114 }
 115
 116 $i = 26;