Python Language
ricorsione

Osservazioni

Somma di numeri da 1 a n

Se volessi scoprire la somma dei numeri da 1 a n dove n è un numero naturale, posso fare 1 + 2 + 3 + 4 + ... + (several hours later) + n . In alternativa, potrei scrivere un ciclo for :

n = 0
for i in range (1, n+1):
    n += i

O potrei usare una tecnica conosciuta come ricorsione:

def recursion(n):
    if n == 1:
        return 1
    return n + recursion(n - 1)

La ricorsione ha vantaggi rispetto ai due metodi precedenti. La ricorsione richiede meno tempo rispetto alla scrittura di 1 + 2 + 3 per una somma da 1 a 3. Per la recursion(4) , la ricorsione può essere utilizzata per lavorare all'indietro:

Chiamate di funzione: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

Mentre il ciclo for sta funzionando rigorosamente in avanti: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). A volte la soluzione ricorsiva è più semplice della soluzione iterativa. Questo è evidente quando si implementa un'inversione di una lista collegata.

Il cosa, come e quando della ricorsione

La ricorsione si verifica quando una chiamata di funzione fa sì che la stessa funzione venga richiamata nuovamente prima che la chiamata della funzione originale termini. Ad esempio, considera la ben nota espressione matematica x! (cioè l'operazione fattoriale). L'operazione fattoriale è definita per tutti gli interi non negativi come segue:

• Se il numero è 0, la risposta è 1.
• Altrimenti, la risposta è quel numero moltiplicato per il fattoriale di un numero inferiore a quel numero.

In Python, un'implementazione ingenua dell'operazione fattoriale può essere definita come una funzione come segue:

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

Le funzioni di ricorsione possono essere difficili da comprendere a volte, quindi passiamo a questa procedura dettagliata. Considera l'espressione factorial(3) . Queste e tutte le chiamate di funzione creano un nuovo ambiente . Un ambiente è fondamentalmente solo una tabella che mappa gli identificatori (ad esempio n , factorial , print , ecc.) Ai loro valori corrispondenti. In qualsiasi momento, è possibile accedere all'ambiente corrente utilizzando i locals() . Nella prima chiamata di funzione, l'unica variabile locale che viene definita è n = 3 . Pertanto, la stampa dei locals() mostrerebbe {'n': 3} . Poiché n == 3 , il valore restituito diventa n * factorial(n - 1) .

A questo punto seguente è dove le cose potrebbero diventare un po 'confuse. Guardando la nostra nuova espressione, sappiamo già che cosa è n . Tuttavia, non sappiamo ancora cosa sia factorial(n - 1) . Innanzitutto, n - 1 restituisce 2 . Quindi, 2 è passato a factorial come valore per n . Poiché si tratta di una nuova chiamata di funzione, viene creato un secondo ambiente per memorizzare questo nuovo n . Sia A il primo ambiente e B il secondo ambiente. Un esiste ancora ed è uguale a {'n': 3} , tuttavia, B (che è uguale a {'n': 2} ) è l'ambiente corrente. Guardando il corpo della funzione, il valore di ritorno è, di nuovo, n * factorial(n - 1) . Senza valutare questa espressione, sostituiamola nell'espressione di ritorno originale. In questo modo, stiamo mentalmente scartando B, quindi ricordatevi di sostituire n conseguenza (cioè i riferimenti a B 's n vengono sostituite con n - 1 che utilizza un' s n ). Ora, l'espressione di ritorno originale diventa n * ((n - 1) * factorial((n - 1) - 1)) . Prenditi un secondo per assicurarti di capire perché è così.

Ora, valutiamo la parte factorial((n - 1) - 1)) di quello. Dal momento che A è n == 3 , stiamo passando a 1 factorial . Pertanto, stiamo creando un nuovo ambiente C che equivale a {'n': 1} . Ancora, il valore restituito è n * factorial(n - 1) . Quindi sostituiamo factorial((n - 1) - 1)) dell'espressione di ritorno "originale" in modo simile a come abbiamo regolato l'espressione di ritorno originale in precedenza. L'espressione "originale" è ora n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .

Quasi fatto. Ora, dobbiamo valutare factorial((n - 2) - 1) . Questa volta, stiamo passando 0 . Pertanto, questo vale 1 . Ora, eseguiamo la nostra ultima sostituzione. L'espressione di ritorno "originale" è ora n * ((n - 1) * ((n - 2) * 1)) . Ricordando che l'espressione di ritorno originale è valutata sotto A , l'espressione diventa 3 * ((3 - 1) * ((3 - 2) * 1)) . Questo, ovviamente, valuta a 6. Per confermare che questa è la risposta corretta, ricorda che 3! == 3 * 2 * 1 == 6 . Prima di leggere ulteriormente, assicurati di comprendere appieno il concetto di ambiente e come si applicano alla ricorsione.

L'istruzione if n == 0: return 1 è chiamata caso base. Questo perché, non mostra alcuna ricorsione. Un caso base è assolutamente necessario. Senza uno, ti imbatterai in una ricorsione infinita. Detto questo, se hai almeno un caso base, puoi avere tutti i casi che vuoi. Ad esempio, potremmo avere factorial scritto in modo equivalente come segue:

def factorial(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Potresti anche avere più casi di ricorsione, ma non entreremo in questo dato che è relativamente raro ed è spesso difficile da elaborare mentalmente.

È anche possibile avere chiamate di funzioni ricorsive "parallele". Ad esempio, considera la sequenza di Fibonacci che è definita come segue:

• Se il numero è 0, la risposta è 0.
• Se il numero è 1, la risposta è 1.
• Altrimenti, la risposta è la somma dei due precedenti numeri di Fibonacci.

Possiamo definire questo è il seguente:

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

Non passerò attraverso questa funzione così accuratamente come ho fatto con factorial(3) , ma il valore di ritorno finale di fib(5) è equivalente alla seguente espressione ( sintatticamente non valida):

(
  fib((n - 2) - 2)
  +
  (
    fib(((n - 2) - 1) - 2)
    +
    fib(((n - 2) - 1) - 1)
  )
)
+
(
  (
    fib(((n - 1) - 2) - 2)
    +
    fib(((n - 1) - 2) - 1)
  )
  +
  (
    fib(((n - 1) - 1) - 2)
    +
    (
      fib((((n - 1) - 1) - 1) - 2)
      +
      fib((((n - 1) - 1) - 1) - 1)
    )
  )
)

Questo diventa (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) che ovviamente valuta a 5 .

Ora, copriamo alcuni termini del vocabolario:

• Una coda di chiamata è semplicemente una chiamata di funzione ricorsiva che è l'ultima operazione da eseguire prima di restituire un valore. Per essere chiari, return foo(n - 1) è una coda, ma return foo(n - 1) + 1 non lo è (poiché l'aggiunta è l'ultima operazione).
• Ottimizzazione chiamata coda (TCO) è un modo per ridurre automaticamente la ricorsione nelle funzioni ricorsive.
• L'eliminazione della chiamata di coda (TCE) è la riduzione di una chiamata di coda a un'espressione che può essere valutata senza ricorsione. TCE è un tipo di TCO.

L'ottimizzazione della chiamata di coda è utile per una serie di motivi:

• L'interprete può minimizzare la quantità di memoria occupata dagli ambienti. Poiché nessun computer dispone di memoria illimitata, le chiamate eccessive di funzioni ricorsive comportano un sovraccarico dello stack .
• L'interprete può ridurre il numero di interruttori dello stack frame .

Python non ha alcuna forma di TCO implementata per una serie di motivi . Pertanto, sono necessarie altre tecniche per superare questa limitazione. Il metodo di scelta dipende dal caso d'uso. Con un po 'di intuizione, le definizioni di factorial e fib possono essere facilmente convertite in codice iterativo come segue:

def factorial(n):
    product = 1
    while n > 1:
        product *= n
        n -= 1
    return product

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

Questo è solitamente il modo più efficace per eliminare manualmente la ricorsione, ma può diventare piuttosto difficile per funzioni più complesse.

Un altro utile strumento è il decoratore lru_cache di Python che può essere utilizzato per ridurre il numero di calcoli ridondanti.

Ora hai un'idea su come evitare la ricorsione in Python, ma quando dovresti ricorrere alla ricorsione? La risposta è "non spesso". Tutte le funzioni ricorsive possono essere implementate in modo iterativo. Si tratta semplicemente di capire come farlo. Tuttavia, ci sono rari casi in cui la ricorsione è a posto. La ricorsione è comune in Python quando gli input previsti non causano un numero significativo di chiamate di funzioni ricorsive.

Se la ricorsione è un argomento che ti interessa, ti imploro di studiare linguaggi funzionali come Scheme o Haskell. In tali lingue, la ricorsione è molto più utile.

Si noti che l'esempio precedente per la sequenza di Fibonacci, sebbene sia efficace nel mostrare come applicare la definizione in python e l'uso successivo della cache lru, ha un tempo di esecuzione inefficiente poiché esegue 2 chiamate ricorsive per ciascun caso non base. Il numero di chiamate alla funzione aumenta esponenzialmente a n .
Piuttosto non intuitivamente, un'implementazione più efficiente userebbe la ricorsione lineare:

def fib(n):
    if n <= 1:
        return (n,0)
    else:
        (a, b) = fib(n - 1)
        return (a + b, a)

Ma quello ha il problema di restituire un paio di numeri. Ciò sottolinea che alcune funzioni in realtà non guadagnano molto dalla ricorsione.

Esplorazione di alberi con ricorsione

Diciamo che abbiamo il seguente albero:

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

Ora, se vogliamo elencare tutti i nomi degli elementi, potremmo farlo con un semplice ciclo. Supponiamo che esista una funzione get_name() per restituire una stringa del nome di un nodo, una funzione get_children() per restituire un elenco di tutti i sub-nodi di un determinato nodo nell'albero e una funzione get_root() per ottenere il nodo radice.

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

Funziona bene e velocemente, ma cosa succede se i sub-nodi hanno dei sub-nodi propri? E quei sub-nodi potrebbero avere più sotto-nodi ... E se non sapessi in anticipo quanti ce ne saranno? Un metodo per risolvere questo è l'uso della ricorsione.

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

Forse non desideri stampare, ma restituisci un elenco semplice di tutti i nomi dei nodi. Questo può essere fatto passando una lista a rotazione come parametro.

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']

Aumentare la profondità massima di ricorsione

C'è un limite alla profondità della possibile ricorsione, che dipende dall'implementazione di Python. Quando viene raggiunto il limite, viene sollevata un'eccezione RuntimeError:

RuntimeError: Maximum Recursion Depth Exceeded

Ecco un esempio di un programma che causerebbe questo errore:

def cursing(depth):
  try:
    cursing(depth + 1) # actually, re-cursing
  except RuntimeError as RE:
    print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!

È possibile modificare il limite di profondità di ricorsione utilizzando

sys.setrecursionlimit(limit) 

Puoi controllare quali sono i parametri attuali del limite eseguendo:

sys.getrecursionlimit()

Eseguendo lo stesso metodo sopra con il nostro nuovo limite otteniamo

sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!

Da Python 3.5, l'eccezione è RecursionError, che deriva da RuntimeError.

Ricorsione di coda - Cattiva pratica

Quando l'unica cosa restituita da una funzione è una chiamata ricorsiva, viene indicata come ricorsione di coda.

Ecco un esempio di conto alla rovescia scritto utilizzando la ricorsione in coda:

def countdown(n):
    if n == 0:
        print "Blastoff!"
    else:
        print n
        countdown(n-1)

Qualsiasi computazione che può essere fatta usando l'iterazione può anche essere fatta usando la ricorsione. Ecco una versione di find_max scritta utilizzando la ricorsione di coda:

def find_max(seq, max_so_far):
    if not seq:
        return max_so_far
    if max_so_far < seq[0]:
        return find_max(seq[1:], seq[0])
    else:
        return find_max(seq[1:], max_so_far)

La ricorsione di coda è considerata una cattiva pratica in Python, dal momento che il compilatore Python non gestisce l'ottimizzazione per le chiamate ricorsive di coda. La soluzione ricorsiva in casi come questo utilizza più risorse di sistema rispetto alla soluzione iterativa equivalente.

Ottimizzazione della ricorsione della coda attraverso l'introspezione della pila

Di default, lo stack di ricorsione di Python non può superare i 1000 frame. Questo può essere modificato impostando sys.setrecursionlimit(15000) che è più veloce, tuttavia, questo metodo consuma più memoria. Invece, possiamo anche risolvere il problema di ricorsione della coda usando l'introspezione dello stack.

#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such 
# exceptions to recall the stack.

import sys

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
  
This function fails if the decorated
function recurses in a non-tail context.
"""
      
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

Per ottimizzare le funzioni ricorsive, possiamo usare il decoratore @tail_call_optimized per chiamare la nostra funzione. Ecco alcuni degli esempi di ricorsione più comuni utilizzando il decoratore sopra descritto:

Esempio fattoriale:

@tail_call_optimized
def factorial(n, acc=1):
  "calculate a factorial"
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.

Esempio di Fibonacci:

@tail_call_optimized
def fib(i, current = 0, next = 1):
  if i == 0:
    return current
  else:
    return fib(i - 1, next, current + next)

print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.