Perché Python ha una profondità di ricorsione massima?

Question

Python ha una profondità di ricorsione massima, ma nessuna profondità di iterazione massima. Perché la ricorsione è limitata? Non sarebbe più naturale trattare la ricorsione come l'iterazione e non limitare il numero di chiamate ricorsive?

Lasciatemi dire che la fonte di questo problema deriva dal tentativo di implementare uno stream (vedere this question per ulteriori dettagli sugli stream). Per esempio, diciamo che vogliamo scrivere un flusso per produrre i numeri naturali:

def stream_accum(s, n): # force the stream to a list of length n 
    def loop(s, acc): 
     if len(acc) == n: 
      return acc 
     hd, tl = s() 
     return loop(tl, acc + [hd]) 
    return loop(s, []) 


def nats(): 
    def loop(n): 
     return n, lambda: loop(n+1) 
    return loop(1) 

La definizione ricorsiva di flussi è abbastanza attraente. Comunque, immagino che l'approccio migliore/più pitoni sarebbe usare i generatori.

Answer 1

Ci sono alcuni problemi qui.

Innanzitutto, come spiega NPE's answer, Python non elimina le chiamate di coda, quindi molte funzioni che consentono una ricorsione illimitata, ad esempio, Scheme sono limitate in Python.

Secondo, come spiegato da NPE, le chiamate che non possono essere eliminate occupano spazio nello stack di chiamate. E, anche nelle lingue che fanno TCE, ci sono un sacco di funzioni ricorsive che non possono essere trattate come l'iterazione. (Considera l'ingenua funzione di Fibonacci che ricorsivamente chiama se stessa due volte.)

Ma perché la chiamata impila una risorsa finita in primo luogo? I frame di stack Python possono essere implementati almeno in linea di principio sullo heap e collegati insieme (vedere Stackless per una dimostrazione dell'esistenza di tale principio) e in uno spazio di memoria a 64 bit, c'è spazio per un numero molto superiore a 1000 frame di stack. (Infatti, anche lo stack C su quasi tutte le piattaforme moderne può contenere molto più di 1000 chiamate ricorsive all'interprete Python.)

Parte del motivo è storico: l'interprete Python standard utilizza lo stack C fisso per chiamarsi in modo ricorsivo ogni volta che si effettua una chiamata ricorsiva ed è stato originariamente progettato per piattaforme a 32 bit (e anche a 24 o 20 bit) in cui lo stack C è piuttosto piccolo.

Ma questo potrebbe essere stato modificato e Python 3.0 sarebbe stato un posto perfetto per cambiarlo. Quindi, perché no? Perché hanno preso una decisione consapevole sul design del linguaggio. Nel codice Pythonic, la ricorsione è generalmente molto superficiale (ad es. Codice come os.walk che attraversa strutture di alberi poco profonde); se la tua funzione raggiunge una profondità di circa 1000, è più probabile che sia un bug piuttosto che essere intenzionale. Quindi, il limite rimane. Ovviamente questo è un po 'circolare - se rimuovono il limite (e, soprattutto, se eliminano le chiamate di coda), una ricorsione più profonda diventerebbe più idiomatica. Ma questo è un po 'il punto - Guido non vuole un linguaggio dove la ricorsione profonda sia idiomatica. (E la maggior parte della comunità Python è d'accordo.)

Answer 2

La ricorsione richiede spazio sul numero call stack, che è di dimensioni limitate. Il codice che utilizza troppi livelli di ricorsione darà un errore chiamato stack overflow (reso famoso anche da some obscure website). Python sembra limitare questo (un po 'arbitrariamente) a 1000 livelli o giù di lì, ma questo can be increased impostando sys.setrecursionlimit.

Iterazione utilizza qualcosa come un for -loop, che viene implementato incrementando alcuni contatori e impostando condizionatamente instruction pointer all'inizio del ciclo. Questo è costante nella memoria.

Answer 3

Questo non è univoco per Python e riguarda ogni chiamata che occupa spazio su call stack e la dimensione della pila è limitata.

Iterazione da sola non consuma spazio nello stack e pertanto non è soggetta a questo limite.

Non tutte le chiamate ricorsive devono consumare spazio nello stack. Ad esempio, alcune lingue possono trasformare automaticamente tail recursion in iterazione. Tuttavia, CPython sceglie di non farlo (Does Python optimize tail recursion?).

È possibile aumentare la profondità massima dello stack di chiamate Python chiamando sys.setrecursionlimit.