Проблема в понимании рекурсии

Question

Попрошу немного подсказок или алгоритм в идеале шаги как решить эту задачу, спасибо

Даны целые числа n, k. (n>=k>=0).
Вычислить

Answer 1

Основа рекурсии - пошаговое уменьшение размера задачи.
Рекурсивный алгоритм состоит из двух частей:

Тривиальный случай
Рекурсивный спуск

Рассмотрим тривиальные случаи нашей задачи:

k == 0, тогда выражение обращается в n!/n! = 1
Основной выход из рекурсии, в принципе его одного достаточно
k == n, выражение => n!/k!, при равных k и n, result = 1
необязательно, но хорошо оптимизирует этот случай
n < 2, n! = 1, k по условию не больше n, result = 1
лишний, k обращается в 0, раньше чем n
k == 1, result = n / 1 = n
лишний пункт, естественным образом разрешится в k == 0 на следующей итерации

Далее рассмотрим спуск:

На каждом шаге будем уменьшать задачу по обоим аргументам.
Для этого результат меньшей задачи F(n-1, k-1) мы будем:

умножать на n, согласно факториалу в числителе.
делить на k, согласно факториалу в знаменателе.

def foo(n, k):
    if k == 0 or k == n:
        return 1

    return n * foo(n - 1, k - 1) // k

# Нарисуем треугольник Паскаля :)
N = 30
pad = 8
for k in range(N):
    for n in range(k, N):
        print(f'{foo(n, k):{pad}}', end=' ')
    print()

Answer 2

указанную функцию можно расписать следующим образом

n(n-1)(n-2)...(n-k+1)/k! = 
= (n-0)(n-1)(n-2)...(n-(k-1))/k =
= [(n-0)/1] * [(n-1)/2] * ... * [(n-(k-1))/k]

отсюда вытекает следующий алгоритм - для для заданного n и k надо считать член

(n-(k-1))/k

и умножать на результат функции для n и k - 1

при этом для k = 0 результат функции равен 1, отсюда код:

def calc(n, k):
    if k == 0:
        return 1

    return calc(n, k - 1) * (n - k + 1) // k

ну или

def calc(n, k):
    return 1 if k == 0 else calc(n, k - 1) * (n - k + 1) // k

БЛОГ НА HUSL

Проблема в понимании рекурсии

Ответы (2 шт):