这种阿克曼函数的实现可以称为尾部递归吗?

Question

我用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) = %dn", m, n, ackermann(&i, &j, a, &len));
    }
  return 0;
}

如果它不是尾递归的，请建议如何使它如此。在C/c++/Java或非函数式编程语言中，任何对Ackermann尾部递归版本的引用都会很好。

Answer 1

你的函数使用一个数据结构来进行回溯，所以虽然它是一个尾部递归函数，但它肯定不是一个简单的递归或迭代过程。数组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;
}

仍然没有任何递归调用，我认为这是一个递归过程

Answer 2

根据定义，您的ackermann函数是尾递归函数，因为您直接返回递归情况的结果。由于没有进一步的逻辑依赖于递归调用的结果，编译器可以安全地应用尾递归优化。