使用链接列表的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在调用中不为空，就应该使用它。