RecursionError: maximum recursion depth exceeded - как преодолеть?

#python #алгоритм #рекурсия

Есть задача в вопросе; есть ее решение, где по изяществу Python "победил" C#, но
вот у же на х=512 вылетает RecursionError:
что посоветуете, отцы? Как преодолеть, если хочется посчитать для х=1024 скажем?

import functools 
from math import sqrt

@functools.lru_cache()
def f(x):
    if x <=1: return 0
    return 1 + min([ f(m + x // m - 2)  for m in range(1,int(sqrt(x))+1) if x%m ==0])


добавлю после первого ответа:   

Кто предложит как изменить алгоритм?

Кстати. Добавил количество рекурсии до 5000. Получается странная фигня. для 1024
считает, делая 3600 итераций, а для 2048 - "выбивает" интерпретатор на 1000+ рекурсии.
Вообще не пойму - в чем проблема....
    

Ответы

Ответ 1

Я python не знаю... Но на С++ решение этой задачи - вот в этом ответе: https://ru.stackoverflow.com/a/770528/195342

Как видите, на ideone решило миллиард за 0.04с без особого напряжения по стеку.

Ключевые моменты:  


Перебор с отсечением  


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


Начинаем со значений, близких к корню  


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


Мемоизация


Позволит не считать повторно то, что уже посчитано. Кстати, подозреваю, что она не
сильно и нужна, но сохранилась с предыдущих попыток решить задачу. Возможно, имеет
смысл заменить массив, все-таки с немалым размером, на map (словарь). Это уже надо
проверять и экспериментировать, но увы, сегодня на это уже нет времени.

Да, это не так красиво выглядит... Но зато решает с очень малой глубиной рекурсии
и очень быстро.

Еще раз извиняюсь за незнание python... Вроде у малого в школе на следующий год обещают
его преподавать - ну, вот тогда придется изучить и исправиться :)

Update

Использовал вместо массива на миллиард байт просто map. На моей
машине миллиард вместо 77ms стал считаться 104ms, но зато при этом потребовалось только
44675 элементов в map. Экономию памяти оцените сами :)

При полном отказе от мемоизации не получается восстановить решение, но сама величина
- 8 - для миллиарда находится за примерно 580ms.


Ответ 2

Судя по всему вы преодолели порог глубины рекурсии.


  exception RecursionError This exception is derived from RuntimeError.
  It is raised when the interpreter detects that the maximum recursion
  depth (see sys.getrecursionlimit()) is exceeded.
  
  New in version 3.5: Previously, a plain RuntimeError was raised.


Ссылка на источник 

Решением вашей проблемы будет ручное указание глубины рекурсии
вызовом метода sys.setrecursionlimit(limit):


  sys.setrecursionlimit(limit)
  
  Set the maximum depth of the Python
  interpreter stack to limit. This limit prevents infinite recursion
  from causing an overflow of the C stack and crashing Python.
  
  The highest possible limit is platform-dependent. A user may need to
  set the limit higher when they have a program that requires deep
  recursion and a platform that supports a higher limit. This should be
  done with care, because a too-high limit can lead to a crash.
  
  If the new limit is too low at the current recursion depth, a
  RecursionError exception is raised.
  
  Changed in version 3.5.1: A RecursionError exception is now raised if
  the new limit is too low at the current recursion depth.


Ну и ссылка на источник.


Ответ 3

Я размещу код, предложенный @Harry на С++, переведенный мною на Python для сохранения
"тематики" языка на странице. Решение принадлежит ему.
В любом случае - как всегда решает на язык, а мозг Ж-)

import numpy as np
from math import sqrt

MAXSIZE = 1000000000
m = np.zeros(MAXSIZE+1, dtype=np.int16)

def f(x, level=0, curmin = MAXSIZE) -> int: 
    if level > curmin: return -1 # Отсечение - нет смысла лезть вглубь
                                 # при наличии более короткого решения
    if x == 1: return 0
    if m[x]: return m[x]      # Сохраненное значение

    res = MAXSIZE;
    for i in range(int(sqrt(x))+1, 0, -1):
        if x%i: continue;
        k = f(i+x//i-2, level+1, res);
        if k < 0: continue;
        if k < res:  res = k
        m[x] = res+1
    return m[x]

n = int(input("дай целое!"))
print( n, ": ", f(n))


вывод подробностей решения:

cur = m[n]
while n>1:
    for i in range(1,int(sqrt(n))+1):
        if n%i: continue
        if m[i+n//i-2] == cur-1:
            n = i+n//i-2
            cur -=1
            print(i, end=' ')
            break
print("")


Разница между этим кодом и кодом приведенным в вопросе - такова.
Он работает для числа 1 000 000 000,  в то время как исходный код "вырубал" интерпретатор
уже на 2048.
Ручное кэширование оказалось надежнее встроенного в пайтон, и - важнее всего -отсечение
неправильных вариантов заметно сократило время.