Как я могу сделать свою рекурсивную программу для вывода факториала числа более эффективной?

Я сделал программу, которая выводит факториал числа, вызывая функцию: factorial(), которая использует рекурсию для вычисления и возврата значения. Я также включил цикл для прерывания программы, когда пользователь вводит слово «выключено». Пожалуйста, предложите какие-либо улучшения

Вот код:

def factorial(base):
    if base == 0 or base == 1:      
        return 1                                  
    else:
        return base * factorial(base - 1)                            


while True:
   base: int = int(input("Enter a base number: "))
   Result = factorial(base)
   print(f"The factorial of {base} is: {Result}")
   offf: str = input("Enter 'off' to terminate calculations: ")
   if offf == "off":
    print("Calculations Terminated")
    break

Вот терминал:

Разве это недостаточно эффективно?

Kelly Bundy 25.10.2022 13:15

@KellyBundy, честно говоря, это довольно неэффективный способ вычисления факториала.

matszwecja 25.10.2022 13:16

@KellyBundy: для вычисления факториалов рекурсия не нужна. Цикл, вероятно, будет немного быстрее, я думаю.

Sergio Tulentsev 25.10.2022 13:16

@matszwecja Как так? Вероятно, результат появляется перед пользователем моментально.

Kelly Bundy 25.10.2022 13:19

@SergioTulentsev Но имеет ли это значение?

Kelly Bundy 25.10.2022 13:19

@KellyBundy Да, это имеет большое значение, тем более что это рекурсивное решение перестает работать около n = 1000. И на самом деле с компьютерами ничего не происходит «мгновенно».

matszwecja 25.10.2022 13:23

@matszwecja: хм, python, должно быть, выделяет крошечный стек. В ruby ​​идентичный код начинает давать сбой при n ≈ 9350.

Sergio Tulentsev 25.10.2022 13:30

@matszwecja Они ничего не сказали о сбое при больших n, так что, вероятно, они этого не делают. И даже factorial(1000) занимает всего около миллисекунды, что всем покажется мгновенным.

Kelly Bundy 25.10.2022 13:31

@SergioTulentsev Python имеет ограничение глубины рекурсии по умолчанию, равное 1000. Его можно изменить, но по умолчанию этот код всегда будет падать около n = 1000, так что это своего рода «жестко запрограммированный» сбой по сравнению с нехваткой памяти программы.

matszwecja 25.10.2022 13:31

@KellyBundy: "Но имеет ли это значение?" - по-видимому, это относится к Silent_Arts

Sergio Tulentsev 25.10.2022 13:31

@SergioTulentsev Я не уверен, что это так, и они не сказали почему, отсюда и мой вопрос. Как насчет того, чтобы просто подождать, пока они ответят? Меня совершенно не интересуют догадки других людей.

Kelly Bundy 25.10.2022 13:32

Рекурсия падает, когда я ввожу что-то около 1000, я думаю, что тогда я просто буду использовать цикл.

Silent_Arts 25.10.2022 13:37
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
12
61
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Хотя рекурсивный подход кажется естественным, к сожалению, он не очень эффективен, так как каждый вызов требует создания отдельного кадра стека. Это также вызывает проблемы из-за ограничения глубины рекурсии Python, что означает, что эта программа будет вызывать исключение для любого base > 1000. Итеративный подход (с циклами) примерно в 2-3 раза быстрее и позволяет избежать проблем с ограничением рекурсии.

def factorial_iterative(base, acc = 1):
    acc = 1
    for i in range(1, base+1):
        acc *= i
    return acc

Обновлено: Конечно, это все еще не превосходит встроенный метод Python math.factorial, который дает нам что-то близкое к 10-кратному ускорению.

Вот результаты для base = 995 и 20000 вызовов функции:

  • рекурсивный: 12,80487060546875 сек.
  • итеративно: 6,284244060516357 сек.
  • math.factorial: 1,1593496799468994 сек.

Предлагаю тоже померить math.factorial.

Kelly Bundy 25.10.2022 13:44

@KellyBundy здесь, вероятно, невероятно сложный анализ различных способов вычисления n! и их эффективность.

matszwecja 25.10.2022 14:07
math.factorial также использует другой алгоритм, который, как мне кажется, имеет лучшую сложность. Поэтому я подозреваю, что при достаточно больших значениях оно превзойдет ваше решение Numba (я не знаком с Numba и пользуюсь только телефоном, иначе я бы сам его протестировал...).
Kelly Bundy 25.10.2022 14:21

Подождите... Это простое использование Numba вообще корректно? Я только что попробовал (в конце концов, на replit.com могу), и он требует 30! отрицательно. Похоже, он использует только 64-битные целые числа.

Kelly Bundy 25.10.2022 14:36

Упс, похоже, что на самом деле это работает только для любых типов C, которые могут обрабатываться. Немного странно, что он не вызывает никаких исключений, хотя

matszwecja 25.10.2022 14:41

Ваше решение Numba, выглядящее значительно быстрее, чем math.factorial кстати, было своего рода намеком на то, что что-то не так, так как это не должно быть возможно :-). (По крайней мере, не с таким простым алгоритмом.) Вот почему я проверил. Кстати, вы перезаписываете второй аргумент, и вы можете начать диапазон с 2.

Kelly Bundy 25.10.2022 14:51

Вы также можете попробовать эту вещь, которая запомнит факториалы.

res_store = [1]
def factorial(num):
    try:
        return num * res_store[num-1]
    except IndexError:
        for i in range(len(res_store), num+1):
            res_store.append(i * res_store[i-1])
        return num * res_store[num-1]

С точки зрения производительности это будет очень быстро, но результат будет сохранен в списке, поэтому он займет память. Для факториала 3000 -> потребление размера будет 26040 байт.

Другие вопросы по теме