Рекурсивная функция для поиска комбинаций без превышения встроенного лимита в Python

Question

Я собрал функцию для поиска комбинаций с использованием рекурсии, не превышая встроенный лимит в python.Например, вы можете рассчитать: выберите (1000, 500).Вот как это выглядит сейчас:

def choose(n, k):
    if not k: 
    return 1 .
elif n < k: 
    return 0
else:
    return ((n + 1 - k) / k) * choose(n, k - 1)

Это работает именно так, как я хочу, чтобы это работало.Если k равно 0, верните 1, а если n меньше, чем k, то верните 0 (это в соответствии с математическими определениями, которые я нашел в википедии).Тем не менее, проблема в том, что я не совсем понимаю последнюю строку (нашел ее во время просмотра веб-страниц).Перед последней строкой, которую я сейчас использую, это была последняя строка, которую я имел в функции:

return choose(n-1,k-1) + choose(n-1, k) 

, которую я также нашел в википедии (хотя я не думаю, что я понимаю эту100% также).Но это всегда приводит к ошибке из-за встроенного ограничения в python, тогда как новая строка, которую я использую, не приводит к такой ошибке.Я понимаю, что новая строка работает намного эффективнее с программой, потому что мы, например, не разбиваем ее на две подзадачи.

Итак, еще раз ... я спрашиваю, есть ли какие-нибудь добрые души, которые могли бы объяснить (понятным образом), как эта строка кода работает в функции:

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

Answer 1

Спойлер : суть в том, что вы должны использовать закрытую форму n! / (k! (n - k)!).

Во многих других языках решение будет заключаться в том, чтобы сделать вашу функцию tail-recursive , хотя Python не поддерживает этот вид оптимизации.Таким образом, реализация рекурсивного решения - просто не лучший вариант.

Вы можете увеличить максимальную глубину рекурсии с sys.setrecursionlimit, но это не оптимально.

Улучшение будетбыть для вычисления n-choose-k с итерацией.

def choose(n, k):
    if n < k:
        return 0

    ans = 1
    while k > 0:
        ans *= (n + 1 - k) / k
        k -= 1

    return ans

Хотя вышеизложенное приведет к ошибке из-за арифметики с плавающей точкой.Таким образом, наилучшим подходом является использование закрытой формы n-choose-k .

from math import factorial

def choose(n, k):
    return factorial(n) / (factorial(k) * factorial(n - k))

Answer 2

Сначала вам нужно узнать, как определяется комбинация C (n, k).Формула для C (n, k):

или, что эквивалентно:

, которая может быть преобразована врекурсивное выражение:

, которое вы реализовали.

Для второго варианта реализации это формула Паскаля .Рекурсивная реализация будет очень медленной (и, возможно, переполнением стека, да).Более эффективной реализацией было бы сохранение каждого C (n, k) в двумерном массиве для вычисления каждого значения по порядку.