7

Максимальная глубина рекурсии: как ее увеличить?

4

У меня есть следующая рекурсивная функция с хвостовой рекурсией:

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 ответ(ов)

0

Я понимаю, что это старая тема, но для тех, кто читает, я бы не рекомендовал использовать рекурсию для подобных задач — списки работают намного быстрее и полностью избегают рекурсии. Я бы реализовал это следующим образом:

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.)

0

У меня была аналогичная проблема с ошибкой "Достигнута максимальная глубина рекурсии". Я обнаружил, что ошибка возникала из-за поврежденного файла в директории, по которой я проходил с помощью os.walk. Если у вас возникают трудности с решением этой проблемы и вы работаете с файловыми путями, обязательно сузьте область поиска, так как это может быть связано с поврежденным файлом.

0

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

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

Этот способ эффективен, так как NumPy использует алгоритм быстрого возведения в степень. Вы получаете результат за O(log n), и это лучше, чем формула Бине, так как работает только с целыми числами. Однако, если вам нужны все числа Фибоначчи до n, то лучше использовать метод мемоизации.

0

Ошибка RecursionError: превышен максимальный предел рекурсии

Решение:

Сначала стоит отметить, что при выполнении рекурсивных функций в Python с большими входными данными (> 10^4) вы можете столкнуться с ошибкой «превышен максимальный предел рекурсии».

Модуль sys в Python содержит функцию getrecursionlimit(), которая покажет текущий предел рекурсии для вашей версии Python.

import sys
print("Лимит рекурсии в Python =", sys.getrecursionlimit())

По умолчанию в некоторых версиях Python этот предел равен 1000, а в других — 1500.

Вы можете изменить это ограничение, но важно помнить, что если вы увеличите его слишком сильно, это может привести к ошибке переполнения памяти. Поэтому будьте осторожны перед его увеличением. Вы можете использовать функцию setrecursionlimit() для изменения этого лимита.

import sys
sys.setrecursionlimit(3000)

Дополнительную информацию о том, что может вызывать эту проблему, вы можете найти по следующей ссылке:

https://elvand.com/quick-sort-binary-search/

0

Многие рекомендуют увеличение предела рекурсии как хорошее решение, однако это не так, поскольку всегда будет существовать ограничение. Вместо этого лучше использовать итеративное решение.

Вот пример итеративного вычисления числа Фибоначчи:

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-ное число Фибоначчи. Это позволяет избежать проблем, связанных с переполнением стека при глубокой рекурсии.

Чтобы ответить на вопрос, пожалуйста, войдите или зарегистрируйтесь