ackermann函数——递归习题算法,数学建模平凡之路-

源于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次。