Как сделать рекурсию с более чем лимитной цифрой?

Question

Я хочу сделать рекурсию с программой ниже, но так как вводимый номер слишком большой (19 цифр). В моей программе выдается ошибка MemoryError: переполнение стека или RecursionError: максимальная глубина рекурсии, превышенная в сравнении . Я пытался сбросить предел рекурсии, используя

import sys
sys.setrecursionlimit(100000)

Но это не помогает. Есть ли у вас какие-либо решения, чтобы справиться с таким большим количеством? Это вся моя программа.

def recursion(n):
    return 1 if n < 2 else n * recursion(n - 2)


string = str(recursion(1000000000000000000))

Answer 1

К сожалению Python не оптимизирует хвостовую рекурсию до итерации. Но вы можете сделать это сами:

def recursion(n):
    result = 1
    for i in range(2, n+1, 2):
        result *= i
    return result

Если вы действительно хотите, чтобы он был рекурсивным, то единственное, что вы можете сделать, это увеличить предел рекурсии и размер стека, но это не очень хорошая идея.

Answer 2

Это одно из практических ограничений рекурсии без оптимизации хвостового вызова .

Python имеет защиту от количества рекурсивных вызовов, которые вы можете сделать, чтобы избежать переполнения стека. Это RecursionError, который вы видите:

Python 3.7.4 (default, Aug 13 2019, 20:35:49) 
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> def recursion(n):
...     return 1 if n < 2 else n * recursion(n - 2)
... 
>>> 
>>> string = str(recursion(1000000000000000000))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in recursion
  File "<stdin>", line 2, in recursion
  File "<stdin>", line 2, in recursion
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded in comparison

Увеличение является возможным решением, но оно удаляет только встроенную защиту. Если будет сделано достаточно рекурсивных вызовов, вам в конечном итоге не хватит памяти, что является второй ошибкой, которую вы получаете (MemoryError: Stack overflow или ошибка сегментации в моем случае).

Python 3.7.4 (default, Aug 13 2019, 20:35:49) 
[GCC 7.3.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.setrecursionlimit(100000)
>>> def recursion(n):
...     return 1 if n < 2 else n * recursion(n - 2)
... 
>>> string = str(recursion(1000000000000000000))
Segmentation fault

Идиоматическое решение этой проблемыпроблема в Python заключается в том, чтобы вместо этого использовать итерацию:

def iteration(n):
    result = 1
    for i in range(n, 1, -2):
        result *= i
    return result

Выполнение этого примера с исходным вводом (1e18) не завершится в ближайшее время. По мере роста целого числа для его вычисления требуется все больше времени, поскольку операции требуют использования целочисленных представлений, больших 64-битных (или скольких битов ваш ЦП может представлять с помощью одного регистра).

Тем не менее,это было бы Pythonic решение этой проблемы.

Answer 3

Для четных n ваша функция вычисляет 2*4*6* ... *n. Легко понять, что это то же самое, что и 2^(n/2) * (n/2)!. Например, 2*4*6*8*10 = (2*1)*(2*2)*(2*3)*(2*4)*(2*5), что, таким образом, 2^5*(1*2*3*4*5) = 32*5!. Это можно быстро и эффективно вычислить с помощью функции:

import math

def f(n):
    k = n//2
    return 2**k * math.factorial(k)

Для нечетных n это немного сложнее. См. этот вопрос из Math Overflow.

По приближение Стирлинга , f(n) асимптотически эквивалентно sqrt(pi*n)*(n/e)^(n/2). Подключив n = 10^18 и взяв журнал результата base-2, вы увидите, что f(10^18) потребуется приблизительно 3,6 эксабайт для хранения полученного целого числа (что, вероятно, больше, чем ваш компьютер может обработать).