May 25, 2012
Our function is a simple transliteration of the mathematical definition into code; note that in the second clause of the
cond it is already known that m is zero:
(define (a m n)
(cond ((zero? m) (+ n 1))
((zero? n) (a (- m 1) 1))
(else (a (- m 1) (a m (- n 1))))))
Here’s an example:
> (a 3 4)
You can run the program at http://programmingpraxis.codepad.org/lLpK9rFw.
Ackermann’s function was important in math, and is also important in computer science, being part of the computation of the time complexity of algorithms such as the disjoint-set data structure and others. It is also used as a test of recursion for compilers.
Pages: 1 2