DjangoBB LoFi version

Полная версия: нехватка памяти для рекурсии

Начало » Python для новичков » нехватка памяти для рекурсии

bor1k_by

Апрель 21, 2016 18:26:24

Всем привет.
Имеется такая функция с рекурсией

def x(a):
    return x(a - 1) + x(a - 2) + 42 if a > 1 else a
print '%r' % x(195)

Довольно странная рекурсия, но рабочая. Не получается только то,что считает максимум для аргумента 30,дальше памяти ,я так понимаю, не хватает, как быть,может кто подскажет?

Firik

Апрель 21, 2016 18:53:50

А задача какая вообще?

FishHook

Апрель 21, 2016 19:15:08

bor1k_by
как быть,может кто подскажет

превращать рекурсию в цикл без рекурсии, это же очевидно.

bor1k_by

Апрель 21, 2016 19:39:24

FishHook

приходило в голову, даже так пробовал

def x(a):
    i=0
    if a > 1:
        while i<=a:
            return (a - 1) + (a - 2) + 42
    else:
        return a
        i=i+1
print x(195)

но это не то что нужно)натолкнете еще на мысль?)

FishHook

Апрель 21, 2016 19:48:20

bor1k_by
как же я вас на мысль натолкну, когда вы не рассказываете что же функция должна сделать.

flasky

Апрель 21, 2016 20:07:09

Одним из вариантом оптимального использования памяти данным скриптом является мемоизация (memoization) (т.е. сохранение результатов выполнения функции для предотвращения повторных вычислений).

Подробнее: https://en.wikipedia.org/wiki/Memoization

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

bor1k_by

Апрель 21, 2016 20:39:18

FishHook
bor1k_byкак же я вас на мысль натолкну, когда вы не рассказываете что же функция должна сделать.

вычислять большие значения аргументов,к примеру, взять результат от a=195

bor1k_by

Апрель 21, 2016 21:01:52

В общем сделал с помощью записи значения в словарь

memo={}
def x(a):
    if a<=1:return a
    if not a in memo:
        memo[a]=x(a-1)+x(a-2)+42
    return memo[a]
print x(195)

py.user.next

Апрель 22, 2016 01:42:40

bor1k_by
Не получается только то,что считает максимум для аргумента 30,дальше памяти ,я так понимаю, не хватает

>>> x(30)
57375296
>>> x(40)
7056700035
>>>

Там не памяти не хватает, а просто слишком много вычислений. x(40) вычислялось несколько минут.