Commit | Line | Data |
5f05dabc |
1 | #!./perl |
2 | |
3 | # |
4 | # test recursive functions. |
5 | # |
6 | |
7 | print "1..23\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 | # For example ackermann(4,0) will take quite a long time. |
26 | # |
27 | # In fact, the current Perl, 5.004, will complain loudly: |
28 | # "Deep recursion on subroutine." (see perldiag) when |
29 | # computing the ackermann(4,0) because the recursion will |
30 | # become so deep (>100 levels) that Perl suspects the script |
31 | # has been lost in an infinite recursion. |
32 | |
33 | sub ackermann ($$) { |
34 | return $_[1] + 1 if ($_[0] == 0); |
35 | return ackermann($_[0] - 1, 1) if ($_[1] == 0); |
36 | ackermann($_[0] - 1, ackermann($_[0], $_[1] - 1)); |
37 | } |
38 | |
39 | # Highly recursive, highly boring. |
40 | |
41 | sub takeuchi ($$$) { |
42 | $_[1] < $_[0] ? |
43 | takeuchi(takeuchi($_[0] - 1, $_[1], $_[2]), |
44 | takeuchi($_[1] - 1, $_[2], $_[0]), |
45 | takeuchi($_[2] - 1, $_[0], $_[1])) |
46 | : $_[2]; |
47 | } |
48 | |
49 | print 'not ' unless (($d = gcd(1147, 1271)) == 31); |
50 | print "ok 1\n"; |
51 | print "# gcd(1147, 1271) = $d\n"; |
52 | |
53 | print 'not ' unless (($d = gcd(1908, 2016)) == 36); |
54 | print "ok 2\n"; |
55 | print "# gcd(1908, 2016) = $d\n"; |
56 | |
57 | print 'not ' unless (($f = factorial(10)) == 3628800); |
58 | print "ok 3\n"; |
59 | print "# factorial(10) = $f\n"; |
60 | |
61 | print 'not ' unless (($f = factorial(factorial(3))) == 720); |
62 | print "ok 4\n"; |
63 | print "# factorial(factorial(3)) = $f\n"; |
64 | |
65 | print 'not ' unless (($f = fibonacci(10)) == 89); |
66 | print "ok 5\n"; |
67 | print "# fibonacci(10) = $f\n"; |
68 | |
69 | print 'not ' unless (($f = fibonacci(fibonacci(7))) == 17711); |
70 | print "ok 6\n"; |
71 | print "# fibonacci(fibonacci(7)) = $f\n"; |
72 | |
73 | $i = 7; |
74 | |
75 | @ack = qw(1 2 3 4 2 3 4 5 3 5 7 9 5 13 29 61); |
76 | |
77 | for $x (0..3) { |
78 | for $y (0..3) { |
79 | $a = ackermann($x, $y); |
80 | print 'not ' unless ($a == shift(@ack)); |
81 | print "ok ", $i++, "\n"; |
82 | print "# ackermann($x, $y) = $a\n"; |
83 | } |
84 | } |
85 | |
86 | ($x, $y, $z) = (18, 12, 6); |
87 | |
88 | print 'not ' unless (($t = takeuchi($x, $y, $z)) == $z + 1); |
89 | print "ok ", $i++, "\n"; |
90 | print "# takeuchi($x, $y, $z) = $t\n"; |