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 12import "runtime" 13 14type Number *Number 15 16// ------------------------------------- 17// Peano primitives 18 19func zero() *Number { 20 return nil 21} 22 23func is_zero(x *Number) bool { 24 return x == nil 25} 26 27func add1(x *Number) *Number { 28 e := new(Number) 29 *e = x 30 return e 31} 32 33func sub1(x *Number) *Number { 34 return *x 35} 36 37func add(x, y *Number) *Number { 38 if is_zero(y) { 39 return x 40 } 41 42 return add(add1(x), sub1(y)) 43} 44 45func mul(x, y *Number) *Number { 46 if is_zero(x) || is_zero(y) { 47 return zero() 48 } 49 50 return add(mul(x, sub1(y)), x) 51} 52 53func fact(n *Number) *Number { 54 if is_zero(n) { 55 return add1(zero()) 56 } 57 58 return mul(fact(sub1(n)), n) 59} 60 61// ------------------------------------- 62// Helpers to generate/count Peano integers 63 64func gen(n int) *Number { 65 if n > 0 { 66 return add1(gen(n - 1)) 67 } 68 69 return zero() 70} 71 72func count(x *Number) int { 73 if is_zero(x) { 74 return 0 75 } 76 77 return count(sub1(x)) + 1 78} 79 80func check(x *Number, expected int) { 81 var c = count(x) 82 if c != expected { 83 print("error: found ", c, "; expected ", expected, "\n") 84 panic("fail") 85 } 86} 87 88// ------------------------------------- 89// Test basic functionality 90 91func init() { 92 check(zero(), 0) 93 check(add1(zero()), 1) 94 check(gen(10), 10) 95 96 check(add(gen(3), zero()), 3) 97 check(add(zero(), gen(4)), 4) 98 check(add(gen(3), gen(4)), 7) 99 100 check(mul(zero(), zero()), 0) 101 check(mul(gen(3), zero()), 0) 102 check(mul(zero(), gen(4)), 0) 103 check(mul(gen(3), add1(zero())), 3) 104 check(mul(add1(zero()), gen(4)), 4) 105 check(mul(gen(3), gen(4)), 12) 106 107 check(fact(zero()), 1) 108 check(fact(add1(zero())), 1) 109 check(fact(gen(5)), 120) 110} 111 112// ------------------------------------- 113// Factorial 114 115var results = [...]int{ 116 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 117 39916800, 479001600, 118} 119 120func main() { 121 max := 9 122 if runtime.GOARCH == "wasm" { 123 max = 7 // stack size is limited 124 } 125 for i := 0; i <= max; i++ { 126 if f := count(fact(gen(i))); f != results[i] { 127 println("FAIL:", i, "!:", f, "!=", results[i]) 128 panic(0) 129 } 130 } 131} 132