使用链表的 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 < 0最多一次递归调用后将使其返回相同的结果，n = 1立即返回cons(1,null) .

每当last在调用中不为 null，您应该使用它。