Maksymalna głębokość rekurencji osiągnięty szybciej przy użyciu functools.lru_cache

Question

Grałem około z memoization i rekursji w Pythonie 3.3

Pomijając fakt, że Python jest niewłaściwy język, że robi to w, odkryłem, że otrzymuję niespójne wyniki między użyciufunctools.lru_cache do memoize i nie używającfunctools.lru_cache

nie zmieniam limit rekurencji - pozostaje on na domyślny, który jest dla mnie 1000.

Aby przetestować ten problem, pisałem nawet prosty funkcji rekurencyjnej do sumy liczb od 1 do I

#!/usr/bin/python 

def sumtil(i): 
"""Recursive function to sum all numbers from 1 through i""" 

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1: 
     return 1 
    else: 
     return i+sumtil(i-1) 

# This will not throw an exception 
sumtil(998) 

# This will throw an exception 
sumtil(999) 

Uruchomienie tej funkcji normalnie mogę uruchomić sumtil(998) wygodnie bez uderzania limit rekurencji. sumtil(999) lub nowsza spowoduje zgłoszenie wyjątku.

Jednak gdy próbuję zdobienia tej funkcji z @functools.lru_cache() wyjątek granica rekurencji jest wyrzucane 3 razy wcześniej, gdy uruchomiony

#!/usr/bin/python 

import functools 

@functools.lru_cache(maxsize=128) 
def sumtil(i): 
    """Recursive function to sum all numbers from 1 through i""" 

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1: 
     return 1 
    else: 
     return i+sumtil(i-1) 

# This will not throw an exception 
sumtil(332) 

# This will throw an exception 
sumtil(333) 

Jako że 332 * 3 = 996, ale 333 * 3 = 999, wydaje mi się, że dekorator lru_cache powoduje, że każdy poziom rekurencji w mojej funkcji staje się trzema poziomami rekursji.

Dlaczego otrzymuję trzykrotnie więcej poziomów rekursji przy użyciu functools.lru_cache do zapamiętania funkcji?

Answer 1

Ponieważ dekorator jest dodatkową funkcją, więc "używa" jednego poziomu w stosie. Przykład:

>>> def foo(f): 
... def bar(i): 
...  if i == 1: 
...  raise Exception() 
...  return f(i) 
... return bar 
... 
>>> @foo 
... def sumtil(i): 
...  if i == 1: 
...   return 1 
...  else: 
...   return i+sumtil(i-1) 
... 
>>> sumtil(3) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 5, in bar 
    File "<stdin>", line 6, in sumtil 
    File "<stdin>", line 5, in bar 
    File "<stdin>", line 6, in sumtil 
    File "<stdin>", line 4, in bar 
Exception 
>>> 

Poza tym, jeśli używa argument packing/unpacking dekorator, to dodatkowy poziom jest używana (choć nie jestem wystarczająco kompetentny o runtime Python, aby wyjaśnić, dlaczego tak się dzieje).

def foo(f): 
    def bar(*args,**kwargs): 
    return f(*args,**kwargs) 
    return bar 

Max. Głębokość rekursji przekroczone:

• undecorated: 1000
• w/o do pakowania: 500
• z wypełnieniem: 334