將遞歸轉換爲'tail遞歸'

Question

我有一個關於如何將'遞歸'轉換爲'尾遞歸'的問題。 這不是一個家庭作業，只是當我試圖拋光算法書遞歸定理時彈出一個問題。 我熟悉使用遞歸（factorial和Fibonacci序列）的2個典型示例，並且也知道如何以遞歸方式和尾遞歸方式實現它們。 我的代碼如下（我使用Perl這只是爲了簡單，但可以很容易地轉換爲C /的Java/C++）

#this is the recursive function 
sub recP { 
    my ($n) = @_; 
    if ($n==0 or $n==1 or $n==2) { 
     return 1; 
    } else { 
     return (recP($n-3)*recP($n-1))+1; 
    } 

} 
for (my $k=1;$k<10;$k++) { 
    print "*"x10,"\n"; 
    print "recP($k)=", recP($k), "\n"; 
} 

運行代碼時，輸​​出如下：

recP(1)=1 
recP(2)=1 
recP(3)=2 
recP(4)=3 
recP(5)=4 
recP(6)=9 
recP(7)=28 
recP(8)=113 
recP(9)=1018 

遞歸函數在返回前用不同的參數調用兩次; 我嘗試了幾種方法將其轉換爲尾部遞歸方式，但都是錯誤的。

任何人都可以看看代碼，並顯示正確的方式，使其尾遞歸？特別是我相信這個樹遞歸轉換有一個例程（在返回之前多次調用遞歸函數），任何人都可以對此有所瞭解嗎？所以我可以用相同的邏輯來處理不同的問題。 在此先感謝。

Answer 1

雖然你經常會看到下面的轉換因子，以尾調用的一個例子：

int factorial(int n, int acc=1) { 
    if (n <= 1) return acc; 
    else  return factorial(n-1, n*acc); 
} 

它並不完全正確的，因爲它需要乘法既關聯和交換。 （乘法是關聯和交換，但上面並沒有作爲其不滿足這些約束等操作的模式。）一個更好的解決方案可能是：

int factorial(int n, int k=1, int acc=1) { 
    if (n == 0) return acc; 
    else  return factorial(n-1, k+1, acc*k); 
} 

這也作爲一個模型爲斐波那契變換：

int fibonacci(int n, int a=1, int b=0) { 
    if (n == 0) return a; 
    else  return fibonacci(n-1, a+b, a); 
} 

注意，這些計算的順序從頭開始，而不是在調用堆棧排隊待審的延續。所以它們在結構上比迭代解決方案更像迭代解決方案。與迭代程序不同，它們從不修改任何變量;所有綁定都是不變的。這是一個有趣和有用的屬性;在這些簡單的情況下，它沒有太大的區別，但是編寫代碼而不用重新分配會使編譯器優化變得更容易。

無論如何，最後一個確實爲您的遞歸函數提供了一個模型;像斐波那契序列，我們需要保持過去相關的價值觀，但我們需要他們三個而不是兩個：

int mouse(int n, int a=1, int b=1, int c=1) { 
    if (n <=2) return a; 
    else  return mouse(n-1, a*c+1, a, b); 
} 

附錄

在評論，兩個問題提出了。我會盡量在這裏回答他們（還有一個）。首先，應該清楚（從考慮沒有函數調用概念的底層機器結構），任何函數調用都可以改寫爲goto（可能帶有非有界中間存儲器）。此外，任何goto都可以表示爲tail-call。所以有可能（但不一定非常漂亮）將任何遞歸重寫爲尾遞歸。

通常的機制是「延續傳遞風格」，這是一種奇特的說法，每次你想調用一個函數時，你將當前函數的其餘部分打包爲新函數（「延續」） ，並將該延續傳遞給被調用的函數。由於每個函數都接收到一個延續作爲參數，所以它必須通過調用它所接收的延續來完成它創建的任何延續。

這可能足以讓你的頭腦旋轉，所以我會換一種方式：不是將參數和返回位置推入堆棧並調用函數（稍後返回），而是推入參數和延續定位到堆棧並轉到一個函數，該函數稍後會轉到繼續位置。簡而言之，你只需將堆棧作爲一個明確的參數，然後你永遠不需要返回。這種編程風格在事件驅動代碼中很常見（請參閱Python Twisted），並且寫入（和讀取）是一種真正的痛苦。所以我強烈建議讓編譯器爲你做這個轉換，如果你能找到一個能做到這一點的轉換。

@xxmouse建議我將遞歸方程從帽子中拉出來，並詢問它是如何派生的。它只是原來的遞歸，但重新作爲一個元組的改造：

fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>

我不知道如果這是再清楚不過，但它是我能做到的最好。看看斐波納契的例子，稍微簡單些。

@j_random_hacker問這個轉換的限制是什麼。它適用於遞歸序列，其中每個元素可以用前面k元素的某個公式表示，其中k是常數。還有其他方法可以產生尾部回叫遞歸。例如：上述

// For didactic purposes only 
bool is_odd(int n) { return n%2 == 1; } 

int power(int x, int n, int acc=1) { 
    if (n == 0)   return acc; 
    else if (is_odd(n)) return power(x, n-1, acc*x); 
    else    return power(x*x, n/2, acc); 
} 

是不一樣的通常非尾部調用遞歸，它不乘法的不同（但等效的和等長的）序列。

int squared(n) { return n * n; } 

int power(int x, int n) { 
    if (n == 0)   return 1; 
    else if (is_odd(n)) return x * power(x, n-1)); 
    else    return squared(power(x, n/2)); 
} 

---

感謝阿列克謝伏龍以下測試： 輸出（ideone）：

mouse(0) = 1 
mouse(1) = 1 
mouse(2) = 1 
mouse(3) = 2 
mouse(4) = 3 
mouse(5) = 4 
mouse(6) = 9 
mouse(7) = 28 
mouse(8) = 113 
mouse(9) = 1018 

Answer 2

使用谷歌，我發現這個網頁，描述Tail Recursion。基本上，您需要將該功能分成至少兩個其他功能：一個執行工作，保留當前值的「累積」，另一個執行工作室功能的驅動程序。 C語言中的階乘例子如下：

/* not tail recursive */ 
unsigned int 
factorial1(unsigned int n) 
{ 
    if(n == 0) 
     return 1; 
    return n * factorial1(n-1); 
} 

/* tail recursive version */ 
unsigned int 
factorial_driver(unsigned int n, unsigned int acc) 
{ 
    if(n == 0) 
     return acc; 

    /* notice that the multiplication happens in the function call */ 
    return factorial_driver(n - 1, n * acc); 
} 

/* driver function for tail recursive factorial */ 
unsigned int 
factorial2(unsigned int n) 
{ 
    return factorial_driver(n, 1); 
} 

Answer 3

你可以做這樣的事情：

#include <stdio.h> 

void fr(int n, int a[]) 
{ 
    int tmp; 

    if (n == 0) 
    return; 

    tmp = a[0] * a[2] + 1; 
    a[2] = a[1]; 
    a[1] = a[0]; 
    a[0] = tmp; 

    fr(n - 1, a); 
} 

int f(int n) 
{ 
    int a[3] = { 1, 1, 1 }; 

    if (n <= 2) 
    return 1; 

    fr(n - 2, a); 

    return a[0]; 
} 

int main(void) 
{ 
    int k; 
    for (k = 0; k < 10; k++) 
    printf("f(%d) = %d\n", k, f(k)); 
    return 0; 
} 

輸出（ideone）：

f(0) = 1 
f(1) = 1 
f(2) = 1 
f(3) = 2 
f(4) = 3 
f(5) = 4 
f(6) = 9 
f(7) = 28 
f(8) = 113 
f(9) = 1018 

編譯器可以轉換fr()弄成這個樣子：

void fr(int n, int a[]) 
{ 
    int tmp; 

label:  

    if (n == 0) 
    return; 

    tmp = a[0] * a[2] + 1; 
    a[2] = a[1]; 
    a[1] = a[0]; 
    a[0] = tmp; 

    n--; 

    goto label; 
} 

這就是尾巴呼叫優化。

Answer 4

@Alexey伏龍芝的答案是好的，但不是精確的權利。確實有可能將任何程序轉換成所有遞歸都是尾遞歸的程序，將其轉換爲Continuation Passing Style。

我現在沒有時間了，但如果我有幾分鐘的時間，會嘗試在CPS中重新實現您的程序。

Answer 5

問題是最後的操作不是遞歸調用之一，而是乘法1的加法。你在C函數：

unsigned faa (int n) // Ordinary recursion 
{ 
    return n<3 ? 1 : 
       faa(n-3)*faa(n-1) + 1; // Call, call, multiply, add 
} 

如果更改這些請求的值的順序，你可以把電話接入環路之一：

unsigned foo (int n) // Similar to tail recursion 
{      // (reverse order) 
    int i; 
    unsigned f; 

    for (i=3, f=1; i<=n; i++) 
     f = f*foo(i-3) + 1; 

    return f; 
} 

的關鍵是在思考的順序這些值實際上是在原始函數中計算的，而不是它們被請求的順序。

請注意，我假設您要刪除一個遞歸調用。如果您希望在函數末尾編寫遞歸調用，希望編譯器爲您優化它，請參閱其他答案。

雖然，「正確的事情（TM）」在這裏做是使用動態規劃來避免計算相同的值多次：

unsigned fuu (int n) // Dynamic programming 
{ 
    int i; 
    unsigned A[4]={1,1,1,1}; 

    for (i=3; i<=n; i++) 
    { 
     memmove (A+1, A, 3*sizeof(int)); 
     A[0] = A[1]*A[3] + 1; 
    } 

    return A[0]; 
} 

陣列A包含所述序列的一個滑動窗口：甲[0] == f（i），A [1] == f（i-1），A [2] == f（i-2）等等。

的memmove可能已經寫爲：

 A[3] = A[2]; 
     A[2] = A[1]; 
     A[1] = A[0];