我用 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;
}
如果它不是尾递归,请提出实现尾递归的方法。在 C/C++/Java 或非函数式编程语言中,任何对 Ackermann 尾递归版本的引用都会很好。
您的函数使用数据结构来进行回溯,因此虽然它是尾递归函数,但它绝对不是一个简单的递归或迭代过程。数组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;
}
仍然没有任何递归调用,我认为这是一个递归过程。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)