Рекурсивные биноминальные коэффициенты Java с использованием связанных списков - PullRequest
Новая
       44

Рекурсивные биноминальные коэффициенты Java с использованием связанных списков

1 голос
/ 04 февраля 2012

В моем классе 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) .....

1 Ответ

0 голосов
/ 04 февраля 2012

Ваш рекурсивный вызов всегда 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 не является нулевым ввызов, вы должны использовать его.

...