blob: 745f5153f6bcf7189af6864066ec597c12d0a8ea [file] [log] [blame]
 // run // Copyright 2009 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. // Test that heavy recursion works. Simple torture test for // segmented stacks: do math in unary by recursion. package main type Number *Number // ------------------------------------- // Peano primitives func zero() *Number { return nil } func is_zero(x *Number) bool { return x == nil } func add1(x *Number) *Number { e := new(Number) *e = x return e } func sub1(x *Number) *Number { return *x } func add(x, y *Number) *Number { if is_zero(y) { return x } return add(add1(x), sub1(y)) } func mul(x, y *Number) *Number { if is_zero(x) || is_zero(y) { return zero() } return add(mul(x, sub1(y)), x) } func fact(n *Number) *Number { if is_zero(n) { return add1(zero()) } return mul(fact(sub1(n)), n) } // ------------------------------------- // Helpers to generate/count Peano integers func gen(n int) *Number { if n > 0 { return add1(gen(n - 1)) } return zero() } func count(x *Number) int { if is_zero(x) { return 0 } return count(sub1(x)) + 1 } func check(x *Number, expected int) { var c = count(x) if c != expected { print("error: found ", c, "; expected ", expected, "\n") panic("fail") } } // ------------------------------------- // Test basic functionality func init() { check(zero(), 0) check(add1(zero()), 1) check(gen(10), 10) check(add(gen(3), zero()), 3) check(add(zero(), gen(4)), 4) check(add(gen(3), gen(4)), 7) check(mul(zero(), zero()), 0) check(mul(gen(3), zero()), 0) check(mul(zero(), gen(4)), 0) check(mul(gen(3), add1(zero())), 3) check(mul(add1(zero()), gen(4)), 4) check(mul(gen(3), gen(4)), 12) check(fact(zero()), 1) check(fact(add1(zero())), 1) check(fact(gen(5)), 120) } // ------------------------------------- // Factorial var results = [...]int{ 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, } func main() { for i := 0; i <= 9; i++ { if f := count(fact(gen(i))); f != results[i] { println("FAIL:", i, "!:", f, "!=", results[i]) panic(0) } } }