t/op/recurse.t

   1 #!./perl
   2
   3 #
   4 # test recursive functions.
   5 #
   6
   7 BEGIN {
   8     chdir 't' if -d 't';
   9     require "./test.pl";
  10     set_up_inc(qw(. ../lib));
  11 }
  12
  13 plan(tests => 28);
  14
  15 use strict;
  16
  17 sub gcd {
  18     return gcd($_[0] - $_[1], $_[1]) if ($_[0] > $_[1]);
  19     return gcd($_[0], $_[1] - $_[0]) if ($_[0] < $_[1]);
  20     $_[0];
  21 }
  22
  23 sub factorial {
  24     $_[0] < 2 ? 1 : $_[0] * factorial($_[0] - 1);
  25 }
  26
  27 sub fibonacci {
  28     $_[0] < 2 ? 1 : fibonacci($_[0] - 2) + fibonacci($_[0] - 1);
  29 }
  30
  31 # Highly recursive, highly aggressive.
  32 # Kids, don't try this at home.
  33 #
  34 # For example ackermann(4,1) will take quite a long time.
  35 # It will simply eat away your memory. Trust me.
  36
  37 sub ackermann {
  38     return $_[1] + 1               if ($_[0] == 0);
  39     return ackermann($_[0] - 1, 1) if ($_[1] == 0);
  40     ackermann($_[0] - 1, ackermann($_[0], $_[1] - 1));
  41 }
  42
  43 # Highly recursive, highly boring.
  44
  45 sub takeuchi {
  46     $_[1] < $_[0] ?
  47         takeuchi(takeuchi($_[0] - 1, $_[1], $_[2]),
  48                  takeuchi($_[1] - 1, $_[2], $_[0]),
  49                  takeuchi($_[2] - 1, $_[0], $_[1]))
  50             : $_[2];
  51 }
  52
  53 is(gcd(1147, 1271), 31, "gcd(1147, 1271) == 31");
  54
  55 is(gcd(1908, 2016), 36, "gcd(1908, 2016) == 36");
  56
  57 is(factorial(10), 3628800, "factorial(10) == 3628800");
  58
  59 is(factorial(factorial(3)), 720, "factorial(factorial(3)) == 720");
  60
  61 is(fibonacci(10), 89, "fibonacci(10) == 89");
  62
  63 is(fibonacci(fibonacci(7)), 17711, "fibonacci(fibonacci(7)) == 17711");
  64
  65 my @ack = qw(1 2 3 4 2 3 4 5 3 5 7 9 5 13 29 61);
  66
  67 for my $x (0..3) {
  68     for my $y (0..3) {
  69         my $a = ackermann($x, $y);
  70         is($a, shift(@ack), "ackermann($x, $y) == $a");
  71     }
  72 }
  73
  74 my ($x, $y, $z) = (18, 12, 6);
  75
  76 is(takeuchi($x, $y, $z), $z + 1, "takeuchi($x, $y, $z) == $z + 1");
  77
  78 {
  79     sub get_first1 {
  80         get_list1(@_)->[0];
  81     }
  82
  83     sub get_list1 {
  84         return [curr_test] unless $_[0];
  85         my $u = get_first1(0);
  86         [$u];
  87     }
  88     my $x = get_first1(1);
  89     ok($x, "premature FREETMPS (change 5699)");
  90 }
  91
  92 {
  93     sub get_first2 {
  94         return get_list2(@_)->[0];
  95     }
  96
  97     sub get_list2 {
  98         return [curr_test] unless $_[0];
  99         my $u = get_first2(0);
 100         return [$u];
 101     }
 102     my $x = get_first2(1);
 103     ok($x, "premature FREETMPS (change 5699)");
 104 }
 105
 106 {
 107     local $^W = 0; # We do not need recursion depth warning.
 108
 109     sub sillysum {
 110         return $_[0] + ($_[0] > 0 ? sillysum($_[0] - 1) : 0);
 111     }
 112
 113     is(sillysum(1000), 1000*1001/2, "recursive sum of 1..1000");
 114 }
 115
 116 # check ok for recursion depth > 65536
 117 {
 118     my $r;
 119     eval {
 120         $r = runperl(
 121                      nolib => 1,
 122                      stderr => 1,
 123                      prog => q{$d=0; $e=1; sub c { ++$d; if ($d > 66000) { $e=0 } else { c(); c() unless $d % 32768 } --$d } c(); exit $e});
 124     };
 125   SKIP: {
 126       skip("Out of memory -- increase your data/heap?", 2)
 127           if $r =~ /Out of memory/i;
 128       is($r, '', "64K deep recursion - no output expected");
 129       is($?, 0, "64K deep recursion - no coredump expected");
 130   }
 131 }
 132