可以阿克曼函数的本次执行被称为尾递归？ [英] Can this implementation of Ackermann function be called tail recursive?

问题描述

我已经写在下面C. code，我们可以把它叫做一个尾递归实现？

I have written following code in C. Can we call it a tail recursive implementation?

#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或无功能的编程语言很好。

If it is not tail-recursive please suggest ways to make it so. Any reference to a tail recursive version of Ackermann would be nice in C/C++/Java or non-functional programming language.

推荐答案

以定义与阿克曼函数的是为你直接返回递归情况下的结果的尾递归函数。由于没有进一步的逻辑取决于你的递归调用的结果，编译器可安全应用尾递归优化。

By definition your ackermann function is a tail-recursive function as you're directly returning the result of the recursive case. Since no further logic depends on the result of your recursive call, the compiler can safely apply tail-recursion optimization.

这篇关于可以阿克曼函数的本次执行被称为尾递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！