源于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 ) = { 0 , y = 0 2 y , x = 0 2 , y = 1 f ( x − 1 , f ( x , y − 1 ) ) ) , e l s e 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 f(x,0)=0
（2） f ( x , 1 ) = 2 f(x,1)=2 f(x,1)=2
（3） f ( 0 , y ) = 2 y 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)) 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(1,10)
f ( 2 , 4 ) f(2,4) f(2,4)
f ( 3 , 3 ) f(3,3) f(3,3)

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

• 先求 f ( x , y − 1 ) = a f(x,y-1)=a f(x,y−1)=a
• 然后求 f ( x − 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 2^{16} 216

可总结出：

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

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

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