Максимальная глубина рекурсии: как ее увеличить?
У меня есть следующая рекурсивная функция с хвостовой рекурсией:
def recursive_function(n, sum):
if n < 1:
return sum
else:
return recursive_function(n-1, sum+n)
c = 998
print(recursive_function(c, 0))
Она работает до значения n=997
, после чего возникает ошибка: RecursionError: maximum recursion depth exceeded in comparison
. Это просто переполнение стека? Есть ли способ обойти эту проблему?
5 ответ(ов)
Я понимаю, что это старая тема, но для тех, кто читает, я бы не рекомендовал использовать рекурсию для подобных задач — списки работают намного быстрее и полностью избегают рекурсии. Я бы реализовал это следующим образом:
def fibonacci(n):
f = [0, 1, 1]
for i in range(3, n):
f.append(f[i-1] + f[i-2])
return '%.0f-й номер Фибоначчи: %.0f' % (n, f[-1])
(Используйте n+1
в range
, если вы начинаете считать последовательность Фибоначчи с 0, а не с 1.)
У меня была аналогичная проблема с ошибкой "Достигнута максимальная глубина рекурсии". Я обнаружил, что ошибка возникала из-за поврежденного файла в директории, по которой я проходил с помощью os.walk
. Если у вас возникают трудности с решением этой проблемы и вы работаете с файловыми путями, обязательно сузьте область поиска, так как это может быть связано с поврежденным файлом.
Если вам нужно получить лишь несколько чисел Фибоначчи, вы можете воспользоваться матричным методом.
from numpy import matrix
def fib(n):
return (matrix('0 1; 1 1', dtype='object') ** n).item(1)
Этот способ эффективен, так как NumPy использует алгоритм быстрого возведения в степень. Вы получаете результат за O(log n), и это лучше, чем формула Бине, так как работает только с целыми числами. Однако, если вам нужны все числа Фибоначчи до n, то лучше использовать метод мемоизации.
Ошибка RecursionError: превышен максимальный предел рекурсии
Решение:
Сначала стоит отметить, что при выполнении рекурсивных функций в Python с большими входными данными (> 10^4) вы можете столкнуться с ошибкой «превышен максимальный предел рекурсии».
Модуль sys в Python содержит функцию getrecursionlimit(), которая покажет текущий предел рекурсии для вашей версии Python.
import sys
print("Лимит рекурсии в Python =", sys.getrecursionlimit())
По умолчанию в некоторых версиях Python этот предел равен 1000, а в других — 1500.
Вы можете изменить это ограничение, но важно помнить, что если вы увеличите его слишком сильно, это может привести к ошибке переполнения памяти. Поэтому будьте осторожны перед его увеличением. Вы можете использовать функцию setrecursionlimit() для изменения этого лимита.
import sys
sys.setrecursionlimit(3000)
Дополнительную информацию о том, что может вызывать эту проблему, вы можете найти по следующей ссылке:
Многие рекомендуют увеличение предела рекурсии как хорошее решение, однако это не так, поскольку всегда будет существовать ограничение. Вместо этого лучше использовать итеративное решение.
Вот пример итеративного вычисления числа Фибоначчи:
def fib(n):
a, b = 1, 1
for i in range(n - 1):
a, b = b, a + b
return a
print(fib(5))
В этом коде мы используем цикл for
, чтобы вычислить n-ное число Фибоначчи. Это позволяет избежать проблем, связанных с переполнением стека при глубокой рекурсии.
Как изменить порядок столбцов в DataFrame?
Получение текущей даты в формате YYYY-MM-DD в Python
Как проверить тип NoneType в Python?
Как удалить пакеты, установленные с помощью easy_install в Python?
Использование @property против геттеров и сеттеров