源于SICP中一道习题。

下面过程计算一个成为Ackermann函数的数学函数：

(define (A x y)
	(cond ((= y 0) 0)
		  ((= x 1) (* 2 y))
		  ((= y 1) 2)
		  (else (A (- x 1)
		           (A x (- y 1))))))

下面各表达式的值是什么：
(A 1 10)
(A 2 4)
(A 3 3)

等价的数学函数表达式为：
$f(x,y)=\left\{\begin{matrix} 0 & ,y=0\\ 2y& ,x=0\\ 2 & ,y=1 \\ f(x-1,f(x, y-1)))& ,else \end{matrix}\right.$f(x,y)=⎩⎪⎪⎨⎪⎪⎧​02y2f(x−1,f(x,y−1)))​,y=0,x=0,y=1,else​
首先，这个函数是用递归定义的。它包含边界值和递归式。

边界值：
（1） $f(x,0)=0$f(x,0)=0
（2） $f(x,1)=2$f(x,1)=2
（3）$f(0,y)=2y$f(0,y)=2y
递归式（递推公式）：
（1）$f(x,y)=f(x-1, f(x, y-1))$f(x,y)=f(x−1,f(x,y−1))

求
(A 1 10)
(A 2 4)
(A 3 3)
等价于求
$f(1,10)$f(1,10)
$f(2,4)$f(2,4)
$f(3,3)$f(3,3)

求$f(x,y)$f(x,y)的步骤：

• 先求$f(x,y-1)=a$f(x,y−1)=a
• 然后求$f(x-1,a)$f(x−1,a)

问题求解如下：

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)
$2^{16}$216

可总结出：

$f(0,n)=2n$f(0,n)=2n

$f(1,n)=f(0,f(1,n-1))=2f(1,n-1)$f(1,n)=f(0,f(1,n−1))=2f(1,n−1)
$=2^2f(1,n-2)=2^{n-1}f(1,1)=2^n$=22f(1,n−2)=2n−1f(1,1)=2n

这个递归函数的设计非常有意思，递归式$f(x,y)=f(x-1, f(x, y-1))$f(x,y)=f(x−1,f(x,y−1))非常像一个查表游戏。把递归计算过程视作查表，有利于理解该函数。
假设这张表（矩阵）是存在的。要求$f(x,y)$f(x,y)，首先要查同一行中的前一个元素$f(x,y-1)$f(x,y−1),然后利用该值到上一行中查找$f(x-1,f(x,y-1))$f(x−1,f(x,y−1))。
例如要求$f(2,4)$f(2,4)，先在表中查找前一个元素$f(2,3)=16$f(2,3)=16，然后在上一行中查找$f(1,16)=2^{16}$f(1,16)=216。
同样求$f(2,5)$f(2,5)，先在表中查找前一个元素$f(2,4)=2^{16}$f(2,4)=216，然后在上一行中查找$f(1,2^{16})=2^{2^{16}}$f(1,216)=2216。

事实上，表是不存在的，在计算$f(x,y-1)=a$f(x,y−1)=a和$f(x-1,a)$f(x−1,a)时同样需要递归求解。而且对于很小的参数值，递归深度已经非常深。例如求$f(2,5)$f(2,5)过程中需要求$f(1,2^{16})$f(1,216)，仅查找同一行内的前一元素$f(x, y-1)$f(x,y−1)就需要$2^{16}$216次。