我用 C 编写了以下代码。我们可以称之为尾递归实现吗?
#include <stdio.h>
int ackermann(unsigned int *m, unsigned int *n, unsigned int* a, int* len)
{
if(!*m && *len == -1) {
return ++*n;
}
else if(!*m && *len >= 0) {
++*n;
*m = a[(*len)--];
}
else if(*n == 0) {
--*m;
*n = 1;
} else {
++*len;
a[*len] = *m - 1;
--*n;
}
return ackermann(m, n, a, len);
}
int main()
{
unsigned int m=4, n=1;
unsigned int a[66000];
int len = -1;
for (m = 0; m <= 4; m++)
for (n = 0; n < 6 - m; n++) {
unsigned int i = m;
unsigned int j = n;
printf("A(%d, %d) = %d\n", m, n, ackermann(&i, &j, a, &len));
}
return 0;
}
如果它不是尾递归的,请提出实现它的方法。任何对 Ackermann 尾递归版本的引用在 C/C++/Java 或非函数式编程语言中都会很好。
最佳答案
您的函数使用数据结构进行回溯,因此虽然它是尾递归函数,但它绝对不是简单的递归或迭代过程。数组 a
充当递归堆栈的角色。你可以一起写出递归调用:
int ackermann(unsigned int *m, unsigned int *n, unsigned int* a, int* len)
{
while (*m || *len != -1) {
if(!*m && *len >= 0) {
*n++;
*m = a[(*len)--];
} else if(*n == 0) {
*m--;
*n = 1;
} else {
++*len;
a[*len] = *m - 1;
*n--;
}
}
return ++*n;
}
仍然没有任何递归调用,我认为这是一个递归过程。
关于这个阿克曼函数的实现可以称为尾递归吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33217360/