fattoriale ricorsivo utilizzando dict provoca RecursionError

Question

Un semplice metodo fattoriale ricorsivo funziona perfettamente:

def fact(n): 
    if n == 0: 
     return 1 
    return n * fact(n-1) 

ma ho voluto sperimentare un po 'e utilizzare un dict invece. A rigor di logica, questo dovrebbe funzionare, ma una serie di dichiarazioni di stampa dirmi che n, invece di fermarsi a 0, scivola verso il basso attraverso i numeri negativi fino al raggiungimento della massima profondità di ricorsione:

def recursive_fact(n): 
    lookup = {0: 1} 
    return lookup.get(n, n*recursive_fact(n-1)) 

Perché?

Answer 1

Python non valuta pigramente i parametri.

Il valore predefinito passato a dict.get chiamata verrà anche valutato prima di chiamare il dict.get.

Quindi, nel tuo caso, il valore predefinito ha una chiamata ricorsiva e poiché la tua condizione non viene mai soddisfatta, esegue una ricorsione infinita.

È possibile confermare questo, con questo programma

>>> def getter(): 
...  print("getter called") 
...  return 0 
... 
>>> {0: 1}.get(0, getter()) 
getter called 
1 

Anche se la chiave 0 esiste nel dizionario, dal momento che tutti i parametri passati alle funzioni in Python saranno valutati, getter è anche invocato, prima che l'attuale dict.get è fatto.

---

Se tutto quello che vogliamo fare è di evitare molteplici valutazioni ricorsive quando i valori sono già valutati, quindi si utilizza functools.lru_cache, se si sta utilizzando Python 3.2+

>>> @functools.lru_cache() 
... def fact(n): 
...  print("fact called with {}".format(n)) 
...  if n == 0: 
...   return 1 
...  return n * fact(n-1) 
... 
>>> fact(3) 
fact called with 3 
fact called with 2 
fact called with 1 
fact called with 0 
6 
>>> fact(4) 
fact called with 4 
24 

Questo decoratore cache semplicemente il risultati per i parametri passati e se viene effettuata di nuovo la stessa chiamata, restituirà semplicemente il valore dalla cache.

---

Se si vuole risolvere la funzione di caching su misura per funzionare, allora avete bisogno di definire il look_up di fuori della funzione, in modo che non verrà creato ogni volta che viene chiamata la funzione.

>>> look_up = {0: 1} 
>>> def fact(n): 
...  if n not in look_up: 
...   print("recursing when n is {}".format(n)) 
...   look_up[n] = n * fact(n - 1) 
...  return look_up[n] 
... 
>>> fact(3) 
recursing when n is 3 
recursing when n is 2 
recursing when n is 1 
6 
>>> fact(4) 
recursing when n is 4 
24 
>>> fact(4) 
24 

altrimenti si può utilizzare il parametro di default, come questo

>>> def fact(n, look_up={0: 1}): 
...  if n not in look_up: 
...   print("recursing when n is {}".format(n)) 
...   look_up[n] = n * fact(n - 1) 
...  return look_up[n]