Aまたはアッカーマン関数

今度はアッカーマン関数だ。Wikipedia の解説を読んでもよくわからないんだけど、引数が大きくなると爆発的に計算量が大きくなるらしい。

(use mymodule)

(define A
  (lambda (n m)
    (cond
      ((zero? n) (add1 m))
      ((zero? m) (A (sub1 n) 1))
      (else (A (sub1 n) (A n (sub1 m)))))))

(print (A 1 0))
(print (A 1 1))
(print (A 2 2))

^o^ > gosh -I. A.scm
2
3
7

といっても、上の例ではすぐに計算が終わって値が返ってくる。ところが (A 4 3) を計算させてみたところ、一晩かかっても終わらなかった。問答では「現実的な問題として、答は得られないでしょう。」と書いてある。
それでもこれは全関数らしい。