递归与分治策略(二)

Ackerman

在这篇文章中,我们将继续介绍递归技术中的一些例子。在上篇文章中,我们介绍了递归在阶乘和Fibonacci数列中的应用。这两个例子也可以用非递归的方式定义

n!=1×2×3×…×(n-1)×n

$$F(n)=\frac{1}{\sqrt{5}}\left [ \left ( \frac{1+\sqrt{5}}{2} \right)^{n+1}-\left ( \frac{1-\sqrt{5}}{2} \right)^{n+1} \right ]$$

但是并非一切递归函数都能用非递归方式定义。接下来将介绍一个更为复杂的递归函数,Ackerman函数。这是一个双递归函数。当一个函数以及它的一个变量由函数自身定义时,称这个函数时双递归函数。

Ackerman函数A(n,m)有两个独立的整形变量m≥0n≥0,其定义如下:

$$\left\{\begin{matrix}
A(1,0)=2 & \\
A(0,m)=1& m\geq 0\\
A(n,0)=n+2& n\geq 2\\
A(n,m)=A(A(n-1,m),m-1) & n,m\geq 1
\end{matrix}\right.$$

排列问题

发表评论

电子邮件地址不会被公开。 必填项已用*标注