0

почему рекурсия выполняется только 995 раз? и как это можно исправить?

5
  • 2
    У Cpython есть ограничение на рекурсию, да, исправить можно с помощью вот этого docs.python.org/3/library/sys.html#sys.setrecursionlimit
    – turkindv
    20 апр 2022 в 6:04
  • 7
    Второй способ - вообще её не использовать. Любой алгоритм (на Python точно) можно написать без неё. Слишком большая вложенность может говорить о неоптимальном алгоритме. 20 апр 2022 в 6:45
  • 1
    Увеличить предел можно попробовать (как - написано выше), но делать это не рекомендуется, потому что если вы не угадаете с лимитом, то при превышении определённого предела вылетит не просто исключение выполнения кода, а конкретно грохнется уже сам интерпретатор питона. В целом, лучше рекурсию в питоне использовать только в учебных целях.
    – CrazyElf
    20 апр 2022 в 7:09
  • а как можно быстро найти факториал большого числа, допустим, 37826497? у рекурсии на столько не растягивается лимит, а через цикл попробовал-слишком долго 😔 20 апр 2022 в 13:20
  • 1
    @артемкостриков А почему вы думаете, что через рекурсию будет быстрее?! ))) Наоборот, при рекурсии будет всегда медленнее, потому что вызовы функции будут забивать данными стек и т.д. Хотел предложить вам использовать библиотеку Numba для ускорения, но для неё это тоже слишком большие числа, переполнение происходит. В простом то питоне целые числа бесконечные, но из-за этого они не оптимальные по скорости.
    – CrazyElf
    20 апр 2022 в 14:25

2 ответа 2

3

Поскольку в комментарии речь зашла про конкретный случай, предлагаю как вариант метод быстрый, но, увы, не сильно точный. Зато считается примерно секунду на предложенном автором вопроса числе:

from numba import njit

@njit()
def factorial(n):
    s = 1
    d = 0
    for i in range(2, n + 1):
        s *= i
        while s >= 10:
            s /= 10
            d += 1
    return s,d

s,d = factorial(37_826_497)
print(f'{s}e+{d}')

Вывод:

4.349383396225913e+270213647
2
  • большое спасибо 20 апр 2022 в 15:19
  • 1
    @артемкостриков Но вы понимаете, что тут только где-то цифр 20 первых от факториала и порядок (степень 10) правильные, а чтобы посчитать прямо все цифры факториала вам придётся всё-таки чистым питоном воспользоваться и долго ждать? )
    – CrazyElf
    20 апр 2022 в 15:26
1

Можно увеличить глубину рекурсии до примерно 22000 (так было когда-то, на Python 3.10 предел 14542 на моей машине). Можно сменить интерпретатор Питона на безстековый - глубина рекурсии будет ограничена только доступной памятью: около 40 миллионов вызовов на 32GB. Последнего числа вам будет достаточно если вы напишете программу достаточно правильно. (Разбор рекурсии)

По времени работы рекурсивная и итеративная программы будут одинаковы: и там и там всё время уйдёт на последовательные умножения. Накладные расходы на цикл или на рекурсию вы даже не заметите.

В соседнем ответе факториал считается приблизительно последовательным умножением и отбрасыванием младших цифр. Ещё один способ - заменить умножение числе на сложение их натуральных логарифмов. Натуральный логарифм перевести в десятичный и напечатать его:

import numpy as np


def big_factorial(n):
    i = np.arange(2, n + 1)
    lg = np.sum(np.log(i)) / np.log(10)
    m, e = np.modf(lg)
    return 10 ** m, int(e)


m, e = big_factorial(int(input()))
print(f'{m}e+{e}')
$ time echo 37826497 | python big-factorial.py
4.349383221475161e+270213647

real  0m1.153s
user  0m1.212s
sys   0m0.552s

Семь знаков этого ответа совпадают с соседним ответом, который, как сейчас станет ясно, более точный.

Можно ли получить точные цифры? Да, можно. Этот код за полтора часа вычисляет факториал и выводит его старшие цифры точно:

import math


n, d = map(int, input().split())
f = math.factorial(n);
e = int(f.bit_length() / math.log(10, 2)) - d
b = 10 ** e
print(f'{f // b}...')
$ time echo 37826497 20 | python big-factorial-exact.py 
434938339623008896624...

real  89m13.142s
user  89m7.112s
sys   0m2.428s

Можно точно оценить интервал в котором лежит факториал. Потребуется меньше минуты:

def factorial(n, d):
    e = 0
    m = 10 ** d
    low = 1
    high = 1
    for i in range(2, n + 1):
        low *= i
        c = 0
        while low >= m:
            low //= 10
            c += 1
        f = 10 ** c
        e += c

        high = (high * i + f - 1) // f
    return low, high, e


n, d = map(int, input().split())
low, high, e = factorial(n, d)
print(low, f'* 10^{e}')
print(high, f'* 10^{e}')
$ time echo 37826497 20 | python big-factorial-interval.py 
43493833962268738973 * 10^270213628
43493833962333044522 * 10^270213628

real  0m47.203s
user  0m47.196s
sys   0m0.000s
2
  • Это в какой версии питона можно до 22000 рекурсию увеличить? Я где пробовал там хорошо если 1500-2000 максимум было, а дальше всё :(
    – CrazyElf
    21 апр 2022 в 6:16
  • 1
    @CrazyElf, глубина 14542 на Python 3.10/Linux 64. 21 апр 2022 в 6:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.