Commit | Line | Data |
---|---|---|
5f05dabc | 1 | #!./perl |
2 | ||
3 | # | |
4 | # test recursive functions. | |
5 | # | |
6 | ||
959e3673 | 7 | print "1..25\n"; |
5f05dabc | 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. | |
5f05dabc | 25 | # |
4fdae800 | 26 | # For example ackermann(4,1) will take quite a long time. |
27 | # It will simply eat away your memory. Trust me. | |
5f05dabc | 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"; | |
959e3673 GS |
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; |