使用鏈接列表的Java遞歸二項式係數

Question

我的compsci UIL類中存在一個挑戰性問題，即使用尾遞歸來獲取給定數字的二項係數列表。我覺得我非常接近，但我在基礎案例中遇到困難。

以下是我的代碼：

public static Cons binomial(int n) 
    { 
     return binomialb(n, null, 1); 

    } 
public static Cons binomialb(int n, Cons last, int power) 
{ 

    if(n == power || n < 0) 
    { 
     return cons(1, null); 
    } 
    else if(last == null) 
    { 
     last = cons(1, cons(1, null)); 
     return binomialb(n-1, last, power); 
    } 
    else 
    { 
     Cons lst = cons(1, null); 
     while(rest(last)!=null) 
     { 
     lst = cons((Integer)first(last)+(Integer)first(rest(last)), lst); 
      last = rest(last); 
     } 
     return binomialb(n-1,lst,power); 
    } 

} 

現在我剛剛得到的（1）.....

Answer 1

你的遞歸調用總是binomialb(n-1,something,power)一個列表，以便改變的唯一的東西是第一個參數n和列表。你最初的電話號碼有power = 1，所以會永遠保持這樣。現在，你的第一個條件是

if (n == power || n < 0) { 
    return cons(1,null); 
} 

如果您最初n > 1稱呼它，電話成爲binomialb(n-k,...,1)爲k = 1, ..., n-1。最後致電binomialb(1,lotsOfWastedWork,1)，很高興回到cons(1,null)。如果您最初使用n < 1與n < 1通話，n < 0將使其在最多一次遞歸調用後返回相同，n = 1立即返回cons(1,null)。

只要last在調用中不爲空，就應該使用它。