1// run
2
3// Copyright 2009 The Go Authors. All rights reserved.
4// Use of this source code is governed by a BSD-style
5// license that can be found in the LICENSE file.
6
7// Test that heavy recursion works. Simple torture test for
8// segmented stacks: do math in unary by recursion.
9
10package main
11
12type Number *Number
13
14// -------------------------------------
15// Peano primitives
16
17func zero() *Number {
18	return nil
19}
20
21func is_zero(x *Number) bool {
22	return x == nil
23}
24
25func add1(x *Number) *Number {
26	e := new(Number)
27	*e = x
28	return e
29}
30
31func sub1(x *Number) *Number {
32	return *x
33}
34
35func add(x, y *Number) *Number {
36	if is_zero(y) {
37		return x
38	}
39
40	return add(add1(x), sub1(y))
41}
42
43func mul(x, y *Number) *Number {
44	if is_zero(x) || is_zero(y) {
45		return zero()
46	}
47
48	return add(mul(x, sub1(y)), x)
49}
50
51func fact(n *Number) *Number {
52	if is_zero(n) {
53		return add1(zero())
54	}
55
56	return mul(fact(sub1(n)), n)
57}
58
59// -------------------------------------
60// Helpers to generate/count Peano integers
61
62func gen(n int) *Number {
63	if n > 0 {
64		return add1(gen(n - 1))
65	}
66
67	return zero()
68}
69
70func count(x *Number) int {
71	if is_zero(x) {
72		return 0
73	}
74
75	return count(sub1(x)) + 1
76}
77
78func check(x *Number, expected int) {
79	var c = count(x)
80	if c != expected {
81		print("error: found ", c, "; expected ", expected, "\n")
82		panic("fail")
83	}
84}
85
86// -------------------------------------
87// Test basic functionality
88
89func init() {
90	check(zero(), 0)
91	check(add1(zero()), 1)
92	check(gen(10), 10)
93
94	check(add(gen(3), zero()), 3)
95	check(add(zero(), gen(4)), 4)
96	check(add(gen(3), gen(4)), 7)
97
98	check(mul(zero(), zero()), 0)
99	check(mul(gen(3), zero()), 0)
100	check(mul(zero(), gen(4)), 0)
101	check(mul(gen(3), add1(zero())), 3)
102	check(mul(add1(zero()), gen(4)), 4)
103	check(mul(gen(3), gen(4)), 12)
104
105	check(fact(zero()), 1)
106	check(fact(add1(zero())), 1)
107	check(fact(gen(5)), 120)
108}
109
110// -------------------------------------
111// Factorial
112
113var results = [...]int{
114	1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
115	39916800, 479001600,
116}
117
118func main() {
119	for i := 0; i <= 9; i++ {
120		if f := count(fact(gen(i))); f != results[i] {
121			println("FAIL:", i, "!:", f, "!=", results[i])
122			panic(0)
123		}
124	}
125}
126