4

次のコードを 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 または非関数型プログラミング言語で適切です。

4

2 に答える 2

4

関数はデータ構造を使用してバックトラッキングを行うため、末尾再帰関数ですが、単純な再帰プロセスまたは反復プロセスではありません。配列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;
}

まだ再帰呼び出しがないので、これを再帰プロセスと見なします。

于 2015-10-19T14:57:59.963 に答える
1

定義上、再帰ケースの結果を直接返すため、ackermann関数は末尾再帰関数です。これ以上のロジックは再帰呼び出しの結果に依存しないため、コンパイラは末尾再帰の最適化を安全に適用できます。

于 2015-10-19T14:57:48.770 に答える