我不知道如何糾正我的尾遞歸（最初的規則遞歸）

Question

我被分配了funct（）並被告知將其轉換爲尾遞歸，所以我做了funct2（）。我使用另一個堆棧溢出thread開始，它有用，但它始終是一個值。

我認爲問題是由於ÿ值爲0最初，和去其他功能的部分時，減去從而不是等同於初始值x。但我不確定。

#include <iostream> 
#include <stdio.h> 
using namespace std; 
int funct(int x); 
int funct2(int x, int y); 

int main() { 

    int x = 24; 

    printf("%d %d", funct(x), funct2(x, 0)); 


} 

int funct(int x) { 

    if (x <= 0){ 
     return 0; 
    } 
    else if (x & 0x01){ 
     return x + funct(x-1); 
    } 
    else { 
     return x - funct(x-1); 
    } 

} 

int funct2(int x, int y) { 

    if (x < 0){ 
     return 0; 
    } 
    else if (x == 0){ 
     return y; 
    } 
    else if (x & 0x01){ 
     return funct2(x-1, y+x); 
    } 
    else { 
     return funct2(x-1, y-(x-1)); 
    } 

} 

任何幫助表示讚賞。多謝你們！

Answer 1

看看this great explanation。由於遞歸步驟不是關聯的，因此只有兩個參數不能實現尾遞歸。考慮通過三個：

int tailrec(int x, int k, int acc) 
    { 
     if (x < 0) { 
      return acc; 
     } 
     if (k & 0x01) { 
      return tailrec(x - 1, k + 1, k + acc); 
     } else { 
      return tailrec(x - 1, k + 1, k - acc); 
     } 
    }