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