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 |
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; |