Ackermann函數的這個實現可以稱爲尾遞歸嗎？

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) = %d\n", m, n, ackermann(&i, &j, a, &len)); 
    } 

    return 0; 
} 

如果不是尾遞歸，請建議如何使它這樣。任何對Ackermann尾遞歸版本的引用在C/C++/Java或非函數式編程語言中都會很好。

Answer 1

通過definition您ackermann功能是尾遞歸函數爲你直接返回遞歸情況下的結果。由於沒有進一步的邏輯取決於遞歸調用的結果，因此編譯器可以安全地應用尾遞歸優化。

Answer 2

你的函數使用數據結構做回溯，所以雖然它是一個尾遞歸函數，但它絕對不是一個簡單的遞歸或迭代過程。數組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; 
} 

仍然沒有任何遞歸調用，我認爲這是一個遞歸過程。