Capire le funzioni ricorsive in Python

Per essere un programmatore professionista, devi essere eccellente nelle basi come variabili, istruzioni condizionali, tipi di dato, specificatori di accesso, chiamate di funzione, scope, ecc. Qualunque sia il tipo di programma che stai scrivendo — che si tratti di un programma per un middleware, per lo sviluppo web o per la data science — queste sono alcune delle nozioni più fondamentali che, come programmatore, devi conoscere molto bene. Sei prima di tutto un programmatore, poi un Data Scientist o uno Sviluppatore Web o un Machine Learning Engineer, ecc.

Uno di questi concetti fondamentali è la ricorsione, ed è estremamente importante quando scrivi funzioni di un certo tipo. Forse già sai che: "Si parla di ricorsione quando una funzione chiama se stessa." Ma cosa succede dietro le quinte? Come viene influenzata la memoria fisica dalla ricorsione? Puoi trasformare qualsiasi funzione in una funzione ricorsiva? In questo tutorial troverai le risposte a queste domande fondamentali.

Anatomia di una funzione ricorsiva:

È probabile che tu abbia già incontrato il termine ricorsione durante i corsi di laurea in Informatica o Ingegneria Informatica. In questa sezione, riprenderai quei concetti ma in modo più interessante. Cominciamo.

Torniamo alla definizione di ricorsione: "Si parla di ricorsione quando una funzione chiama se stessa". Prendiamo un esempio per supportare questa definizione:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Puoi vedere che la funzione A() viene chiamata da se stessa. Questo è un esempio di ricorsione, e A() è una funzione ricorsiva.

Ora vediamo alcune basi di una funzione ricorsiva.

Basi di una funzione ricorsiva:

Una funzione ricorsiva deve contenere le seguenti due proprietà:

• Una relazione di ricorrenza
• Una condizione di terminazione

Considera il frammento di codice sopra per comprendere questi punti. Chiaramente, la funzione ha una specifica relazione di ricorrenza:

$n\le 1$ è la condizione di terminazione / condizione di ancoraggio / condizione base e, se soddisfatta, la ricorsione si interrompe. Specificare questa condizione è imprescindibile. Altrimenti, la funzione cadrà in un loop infinito.

(Nota che il frammento di codice sopra non segue un linguaggio di programmazione particolare. L’intento principale qui è mostrare un esempio di funzione ricorsiva.)

Ora potresti chiederti perché mai qualcuno dovrebbe scrivere una funzione ricorsiva se esistono alternative migliori. Sì, a volte risulta difficile seguire il flusso di una ricorsione, ma una volta fatta pratica, scoprirai che la ricorsione è elegante in termini di leggibilità del programma e gestione delle variabili. La ricorsione non ha bisogno di variabili extra per essere eseguita, ma richiede una corretta condizione di terminazione per fermarsi. Spesso è difficile trovare la condizione di terminazione di una ricorsione. Ancora una volta, "La pratica rende perfetti". Più avanti in questo tutorial, vedrai quanto può essere bello e compatto un programma se implementato con la ricorsione rispetto ai mezzi convenzionali. Ora passerai a studiare la rappresentazione in memoria di una funzione ricorsiva.

Rappresentazione in memoria di una funzione ricorsiva:

In questa sezione studierai come le funzioni ricorsive sono rappresentate fondamentalmente in memoria mediante alberi e stack. Considera la seguente funzione ricorsiva A() per capirlo:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Per prima cosa, capirai la rappresentazione in memoria usando gli alberi. Potrebbe sembrare un po’ difficile, ma è davvero semplice. Se dovessi scrivere ogni chiamata di funzione in modo simile a un albero, come apparirebbe?

Qualcosa del genere?

Alcuni punti da notare qui:

• La funzione è chiamata con A(3) e per questo vengono effettuate 4 (3+1) chiamate di funzione. Generalizzando, se viene chiamata A(n), allora saranno necessarie in totale (n+1) chiamate di funzione.
• Le chiamate P() sono le stampe prodotte da print(n).
• La funzione si è fermata con la chiamata A(0) poiché l’istruzione if (dopo la chiamata A(0)) riceverà n < 1, il che causerà la terminazione della funzione.

Hai visto prima questa rappresentazione ad albero perché, per rappresentare una funzione ricorsiva su uno stack, questa rappresentazione è necessaria. Ora lo vedrai.

(Uno stack è una struttura dati che segue l’ordine LIFO, last in first out)

Per la rappresentazione con lo stack, dovrai attraversare l’albero dall’alto verso il basso e da sinistra a destra. La seguente immagine lo chiarirà.

Interpretiamo questo strano oggetto (l’albero). Tieni presente che uno stack consiste di due operazioni: 1. Push, con cui inserisci un elemento nello stack; 2. Pop, con cui estrai un elemento dallo stack.

Ora inizi l’attraversamento dell’albero dall’alto verso il basso e da sinistra a destra:

• Ogni volta che vedi una chiamata di funzione, la inserirai nello stack (push).
• Se vedi una chiamata a print()/P(), stamperai semplicemente l’elemento corrispondente di conseguenza.

Di seguito trovi gli elementi dello stack risultanti dall’attraversamento dell’albero da A(3) a A(0) solo in direzione dall’alto verso il basso:

Ora inizi la seconda metà dell’attraversamento dell’albero, cioè l’ordine da sinistra a destra. Ogni volta che vedi una chiamata di funzione per la seconda volta, la estrarrai (pop). Sorprendentemente, il primo elemento dello stack (A(0)) che verrà estratto era l’ultimo ad essere entrato nello stack (LIFO, ricordi?). Ora, lungo il percorso incontrerai tre chiamate P() — P(1), P(2) e P(3). Le stamperai nell’ordine in cui compaiono durante l’attraversamento. L’ordine sarà:

Infine, quando termini il processo di attraversamento, lo stack sarà completamente vuoto. Per comprendere ancora meglio l’operazione di pop, ecco un’immagine dello stack dopo essere stato completamente svuotato.

Hai visto come rappresentare una semplice funzione ricorsiva in memoria usando un albero e uno stack. Ora vedrai come tracciare una ricorsione.

Tracciare una ricorsione:

In questa sezione imparerai come puoi tracciare una ricorsione in modo metodico. Considera la seguente funzione ricorsiva:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Un punto cruciale qui è che ogni volta che una funzione viene chiamata, in memoria viene creato un record di attivazione che contiene le variabili locali di quella funzione e un puntatore all’istruzione (che indica la prossima operazione da eseguire quando il controllo ritorna a quella funzione). Supponiamo che una funzione chiamata main() abbia chiamato la funzione A() come A(3). Numeriamo le righe di A() a partire dall’istruzione if per una migliore comprensione:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

I record di attivazione apparirebbero così:

Come detto in precedenza, le funzioni hanno le loro copie delle variabili locali e dei puntatori all’istruzione (in questo caso il numero di riga). Dopo A(0) la funzione A() terminerà e avverrà il pop. Nota che qui è usato uno stack orizzontale, che è esattamente lo stesso di quelli che hai visto in precedenza nel tutorial. Mentre i record vengono inseriti nello stack, avverranno anche le stampe e verranno stampati i seguenti elementi:

I puntatori all’istruzione sono fondamentali da notare qui perché spesso in una funzione ricorsiva il controllo torna alla stessa funzione ma con un valore di variabile diverso. Quindi, per mantenere tutto sincronizzato, questi puntatori sono davvero utili. Puoi seguire esattamente questo processo per tracciare una ricorsione usando una rappresentazione ad albero.

Ora studierai come eseguire un’analisi spazio-temporale di una funzione ricorsiva.

Analisi spazio-temporale di una funzione ricorsiva:

DataCamp ha un ottimo articolo sull’Analisi asintotica in Python, ed è consigliabile dargli un’occhiata prima di leggere questa sezione. Ricapitoliamo velocemente cosa si intende per analisi dello spazio e del tempo di una funzione (note anche come complessità spaziale e complessità temporale):

Dato un input, una funzione dovrebbe produrre un certo output. Per farlo, quanto tempo impiega la funzione? La misura della complessità temporale approssima questo tempo ed è anche chiamata runtime della funzione. Allo stesso modo, la misura della complessità spaziale approssima lo spazio (memoria) richiesto da una funzione, cioè per un dato input. Ma perché sono necessarie?

• Invece di eseguire una funzione su una gamma di input di dimensioni variabili, puoi facilmente approssimare come potrebbe comportarsi su input di dimensioni diverse.
• Se hai due funzioni che soddisfano lo stesso obiettivo, quale sceglierai? Quali misure considererai per prendere la decisione? Sì, esatto. Le confronterai analizzando le loro complessità spaziale e temporale e vedrai quale si comporta meglio.

Prendiamo ora una semplice funzione ricorsiva e analizziamone la complessità in spazio e tempo.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Facciamo prima l’analisi della complessità temporale. Supponi che il tempo totale impiegato dalla funzione A() sopra sia $T(n)$. Ora $T(n)$ è la somma del tempo impiegato per confrontare se n è maggiore di 1 e del tempo impiegato per eseguire A(n-1). Quindi, $T(n)$ può essere espresso come -

1 è il tempo impiegato per il confronto (puoi mettere qualsiasi costante). Ora, quale sarà il tempo (in termini di $T(n)$) per eseguire A(n-1)?

Allo stesso modo,

e così via.

Se presti attenzione alle equazioni, sono tutte collegate. Non è così? Se le sostituisci una dopo l’altra, ottieni -

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (dopo aver fatto girare la funzione per k termini)

Ora devi determinare in quale punto la funzione si fermerà. Secondo la condizione di ancoraggio data, puoi scrivere -

Supponi che, dopo k termini, la funzione smetta di girare. Se è così, allora deve valere -

$n - k = 1 => k = n - 1$

Ora, sostituendo il valore di k (= n - 1) in $T(n) = k + T(n-k)$:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Per T(1) è richiesto solo il confronto

Per la regola dell’analisi asintotica, $T(n) = n$ può essere riscritto come $T(n) = \mathcal{O}(n)$. Ciò significa che la complessità temporale (nel caso peggiore) della funzione è $\mathcal{O}(n)$.

Potresti voler rallentare un po’ qui e osservare attentamente ogni passaggio di questo processo. È altamente consigliato farlo con carta e penna per comprenderlo fino in fondo.

L’analisi della complessità spaziale della funzione è semplice. La funzione è in memoria e non fa uso di variabili extra. Quindi, puoi concludere che la complessità spaziale della funzione è $\mathcal{O}(n)$.

Ora metterai insieme tutto questo e implementerai una semplice funzione ricorsiva in Python.

Implementare una semplice funzione ricorsiva in Python:

Scriverai una funzione ricorsiva per trovare il fattoriale di un numero dato. Poi scriverai una versione iterativa della stessa funzione. Cominciamo.

# Recursive function factorial_recursion()

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

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

Ricordi i due ingredienti chiave per scrivere una funzione ricorsiva?

• Relazione di ricorrenza
• Condizione di terminazione

In questo caso, la relazione di ricorrenza può essere:

$f(n) = n!$
$f(n) = n * f(n-1)$ e così via.

La condizione di terminazione è quando n è uguale a 1.

Semplice, no?

Ora implementerai la versione iterativa della stessa funzione.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

La differenza tra le due versioni è evidente. Quella ricorsiva è molto più elegante di quella iterativa. Non trovi?

Complimenti!

Sei arrivato fino in fondo. In questo tutorial hai fatto uno studio approfondito delle funzioni ricorsive. Dalle basi assolute fino all’analisi delle complessità in spazio e tempo di una funzione ricorsiva, hai coperto tutto. Hai anche visto come la ricorsione possa essere utile per risolvere problemi con una certa caratteristica. Ora dovresti essere in grado di risolvere problemi (che hanno una relazione di ricorrenza e una condizione di terminazione) usando la ricorsione. Potresti provare a risolvere il problema di trovare i Numeri di Fibonacci in un intervallo usando la ricorsione.

Ti invito a risolvere alcuni problemi comuni come Binary Search, Merge Sort, Torre di Hanoi, ecc. usando la ricorsione ed eseguire anche un’analisi spazio-temporale. Questo ti renderà certamente un programmatore migliore.

Da un punto di vista introduttivo, quanto trattato è sufficiente. Ma se vuoi studiare di più sulla ricorsione, assicurati di visitare i seguenti link:

• Recursion and Dictionaries del Prof. Grimson
• Programmazione dinamica per ottimizzare le prestazioni delle funzioni ricorsive

Se vuoi imparare di più su Python, segui il corso gratuito di DataCamp Intro to Python for Data Science.