使用链表的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调用它，则对于k = 1, ..., n-1，调用将变为binomialb(n-k,...,1)。最后，调用是binomialb(1,lotsOfWastedWork,1)，它将愉快地返回cons(1,null)。如果最初用n < 1调用它，n < 0将使它在最多一次递归调用后返回相同的值，n = 1立即返回cons(1,null)。

无论何时last在调用中不为空，都应该使用它。