Как работает этот рекурсивный алгоритм?

Question

[Матвей Тарасов]

Здравствуйте!
Алгоритм подсчета бинома, как я понимаю, по формуле Бернули.

Также он использует рекурентную формулу нахождения кол-ва сочетаний

Сам алгоритм:

public double binomial1(int N, int k, double p) {
        if (N == 0 && k == 0) return 1.0;
        if (N < 0 || k < 0) return 0.0;
        return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }

Вопросы:
Как так получается, что у нас (1.0 - p) и p в рекурентном выражении без степеней? Ведь по формуле Бернули должны быть. Я понимаю, что там в рекурсии, видимо, они несколько раз сами на себя умножаются, но распутать клубок не могу?
Есть ли какие-то методы для анализа подобных алгоритмов/формул, и для создания этих формул. Как-то ведь до написания подобного кода люди доходят?

Сам код взял из книги Седжвика по алгоритмам, начал проходить курс на coursera.

Comments

[Lynn «Кофеман»]

Возьмите какие-нибудь небольшие N и k и распишите вручную что и как вызывается

[Матвей Тарасов]

Я это сделал, в итоге верный алгоритм и кол-во множителей тоже верное, но я не понимаю, как вот человек сидел и превратил формулы выше в в такой вот алгоритм

[Lynn «Кофеман»]

Собственно простое преобразование:

[Матвей Тарасов]

Спасибо огромное! Очень полезно, разобрался и понял все, что-то даже в голову не пришло на бумажке раскрыть формулу

Answer 1

[Myclass]

А вы понимаете слово степень?
Ведь это просто n-ое кол-во раз число умножается на себя. И первая часть до плюса это и воспроизводит. Вторая часть после плюса есть и есть тот плюс из формулы.

Comments

[Матвей Тарасов]

Вы понимаете, что можно отвечать на вопросы без агрессивных выпадов? Конечно, я понимаю, что такое степень, и ваше объяснение мне нисколько не помогло, в отличии от действительно полезного ответа в комментариях.

[mkone112]

Матвей Тарасов,

Вы понимаете, что можно отвечать на вопросы без агрессивных выпадов?

Не знаю понимает ли, но именно это он и сделал.

[Николай Савельев]

Матвей Тарасов, где ты здесь увидел агрессивные выпады?

[Матвей Тарасов]

Да, я не прав. Извините. Спасибо за ответ в любом случае!

Answer 2

[Николай Савельев]

Подобные алгоритмы легко анализируются и распутываются, когда начинаешь вручную подставлять значения. 0, 1, 2,...