La ricorsione è un concetto fondamentale in informatica e matematica che consente alle funzioni di richiamarsi, consentendo la soluzione di problemi complessi attraverso passaggi iterativi. Una rappresentazione visiva comunemente utilizzata per comprendere e analizzare l'esecuzione di funzioni ricorsive è un albero di ricorsione. In questo articolo esploreremo la teoria alla base degli alberi di ricorsione, la loro struttura e il loro significato nella comprensione degli algoritmi ricorsivi.

Cos'è un albero di ricorsione?

Un albero di ricorsione è una rappresentazione grafica che illustra il flusso di esecuzione di una funzione ricorsiva. Fornisce una suddivisione visiva delle chiamate ricorsive, mostrando la progressione dell'algoritmo man mano che si ramifica e infine raggiunge un caso base. La struttura ad albero aiuta ad analizzare la complessità temporale e a comprendere il processo ricorsivo coinvolto.

Struttura ad albero

Ogni nodo in un albero di ricorsione rappresenta una particolare chiamata ricorsiva. La chiamata iniziale è raffigurata in alto, mentre le chiamate successive si ramificano sotto di essa. L'albero cresce verso il basso, formando una struttura gerarchica. Il fattore di ramificazione di ciascun nodo dipende dal numero di chiamate ricorsive effettuate all'interno della funzione. Inoltre, la profondità dell'albero corrisponde al numero di chiamate ricorsive prima di raggiungere il caso base.

Caso base

Il caso base funge da condizione di terminazione per una funzione ricorsiva. Definisce il punto in cui la ricorsione si interrompe e la funzione inizia a restituire valori. In un albero di ricorsione, i nodi che rappresentano il caso base sono solitamente rappresentati come nodi foglia, poiché non danno luogo a ulteriori chiamate ricorsive.

Chiamate ricorsive

I nodi figli in un albero di ricorsione rappresentano le chiamate ricorsive effettuate all'interno della funzione. Ogni nodo figlio corrisponde a una chiamata ricorsiva separata, che porta alla creazione di nuovi sottoproblemi. I valori o parametri passati a queste chiamate ricorsive possono differire, portando a variazioni nelle caratteristiche dei sottoproblemi.

Flusso di esecuzione:

L'attraversamento di un albero di ricorsione fornisce informazioni dettagliate sul flusso di esecuzione di una funzione ricorsiva. Partendo dalla chiamata iniziale al nodo radice, seguiamo i rami per raggiungere le chiamate successive fino ad incontrare il caso base. Quando vengono raggiunti i casi base, le chiamate ricorsive iniziano a ritornare e i rispettivi nodi nell'albero vengono contrassegnati con i valori restituiti. L'attraversamento continua finché non è stato attraversato l'intero albero.

Analisi della complessità temporale

Gli alberi di ricorsione aiutano ad analizzare la complessità temporale degli algoritmi ricorsivi. Esaminando la struttura dell'albero, possiamo determinare il numero di chiamate ricorsive effettuate e il lavoro svolto ad ogni livello. Questa analisi aiuta a comprendere l'efficienza complessiva dell'algoritmo e a identificare eventuali potenziali inefficienze o opportunità di ottimizzazione.

introduzione

• Pensa a un programma che determina il fattoriale di un numero. Questa funzione accetta un numero N come input e restituisce come risultato il fattoriale di N. Lo pseudocodice di questa funzione sarà simile a:

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• La ricorsione è esemplificata dalla funzione menzionata in precedenza. Stiamo invocando una funzione per determinare il fattoriale di un numero. Quindi, dato un valore minore dello stesso numero, questa funzione richiama se stessa. Questo continua finché non raggiungiamo il caso base, in cui non ci sono più chiamate di funzione.
• La ricorsione è una tecnica per gestire problemi complicati quando il risultato dipende dai risultati di istanze più piccole dello stesso problema.
• Se pensiamo alle funzioni, una funzione si dice ricorsiva se continua a chiamare se stessa finché non raggiunge il caso base.
• Qualsiasi funzione ricorsiva ha due componenti principali: il caso base e il passaggio ricorsivo. Smettiamo di passare alla fase ricorsiva una volta raggiunto il caso base. Per evitare una ricorsione infinita, i casi base devono essere adeguatamente definiti e sono cruciali. La definizione di ricorsione infinita è una ricorsione che non raggiunge mai il caso base. Se un programma non raggiunge mai il caso base, continuerà a verificarsi un overflow dello stack.

Tipi di ricorsione

In generale, esistono due diverse forme di ricorsione:

• Ricorsione lineare
• Ricorsione dell'albero
• Ricorsione lineare

Ricorsione lineare

• Una funzione che richiama se stessa una sola volta ogni volta che viene eseguita si dice che sia linearmente ricorsiva. Un bell'esempio di ricorsione lineare è la funzione fattoriale. Il nome 'ricorsione lineare' si riferisce al fatto che una funzione linearmente ricorsiva richiede una quantità lineare di tempo per essere eseguita.
• Dai un'occhiata allo pseudo-codice qui sotto:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Se guardiamo la funzione faiSomething(n), accetta un parametro chiamato n ed esegue alcuni calcoli prima di chiamare nuovamente la stessa procedura ma con valori inferiori.
• Quando il metodo doSomething() viene chiamato con il valore di argomento n, diciamo che T(n) rappresenta la quantità totale di tempo necessaria per completare il calcolo. Per questo possiamo anche formulare una relazione ricorrente, T(n) = T(n-1) + K. K qui serve come costante. La costante K è inclusa perché la funzione impiega tempo per allocare o deallocare memoria a una variabile o eseguire un'operazione matematica. Usiamo K per definire l'ora poiché è così piccola e insignificante.
• La complessità temporale di questo programma ricorsivo può essere semplicemente calcolata poiché, nello scenario peggiore, il metodo doSomething() viene chiamato n volte. Formalmente parlando, la complessità temporale della funzione è O(N).

Ricorsione dell'albero

• Quando si effettua una chiamata ricorsiva nel caso ricorsivo più di una volta, si parla di ricorsione dell'albero. Un esempio efficace della ricorsione dell'albero è la sequenza di Fibonacci. Le funzioni ricorsive dell'albero operano in tempo esponenziale; non sono lineari nella loro complessità temporale.
• Dai un'occhiata allo pseudo-codice qui sotto,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• L'unica differenza tra questo codice e il precedente è che questo effettua una chiamata in più alla stessa funzione con un valore inferiore a n.
• Mettiamo T(n) = T(n-1) + T(n-2) + k come relazione di ricorrenza per questa funzione. K serve ancora una volta come costante.
• Quando viene eseguita più di una chiamata alla stessa funzione con valori più piccoli, questo tipo di ricorsione è nota come ricorsione ad albero. L’aspetto intrigante ora è: quanto tempo richiede questa funzione?
• Fai un'ipotesi basata sull'albero di ricorsione riportato di seguito per la stessa funzione.
  
• Potrebbe capitarti che sia difficile stimare la complessità temporale osservando direttamente una funzione ricorsiva, in particolare quando si tratta di una ricorsione su albero. Il metodo dell'albero di ricorsione è una delle numerose tecniche per calcolare la complessità temporale di tali funzioni. Esaminiamolo più nel dettaglio.

Cos'è il metodo dell'albero di ricorsione?

• Le relazioni ricorrenti come T(N) = T(N/2) + N o le due trattate in precedenza nella sezione sui tipi di ricorsione vengono risolte utilizzando l'approccio dell'albero di ricorsione. Queste relazioni ricorrenti spesso utilizzano una strategia divide et impera per affrontare i problemi.
• Ci vuole tempo per integrare le risposte ai sottoproblemi più piccoli che si creano quando un problema più grande viene suddiviso in sottoproblemi più piccoli.
• La relazione di ricorrenza, ad esempio, è T(N) = 2 * T(N/2) + O(N) per l'ordinamento Merge. Il tempo necessario per combinare le risposte a due sottoproblemi con una dimensione combinata di T(N/2) è O(N), il che è vero anche a livello di implementazione.
• Ad esempio, poiché la relazione di ricorrenza per la ricerca binaria è T(N) = T(N/2) + 1, sappiamo che ogni iterazione della ricerca binaria risulta in uno spazio di ricerca tagliato a metà. Una volta determinato il risultato, usciamo dalla funzione. Alla relazione di ricorrenza è stato aggiunto +1 perché si tratta di un'operazione a tempo costante.
• La relazione di ricorrenza T(n) = 2T(n/2) + Kn è da considerare. Kn denota la quantità di tempo necessaria per combinare le risposte a sottoproblemi n/2 dimensioni.
• Descriviamo l'albero di ricorsione per la suddetta relazione di ricorrenza.

Possiamo trarre alcune conclusioni dallo studio dell'albero di ricorsione sopra, incluso

1. L’entità del problema a ciascun livello è tutto ciò che conta per determinare il valore di un nodo. La dimensione del problema è n al livello 0, n/2 al livello 1, n/2 al livello 2 e così via.

2. In generale, definiamo l'altezza dell'albero come uguale a log (n), dove n è la dimensione del problema, e l'altezza di questo albero di ricorsione è uguale al numero di livelli nell'albero. Questo è vero perché, come abbiamo appena stabilito, la strategia divide et impera viene utilizzata dalle relazioni ricorrenti per risolvere i problemi, e passare dalla dimensione del problema n alla dimensione del problema 1 richiede semplicemente l'esecuzione di log (n) passaggi.

• Consideriamo ad esempio il valore di N = 16. Se possiamo dividere N per 2 ad ogni passo, quanti passi sono necessari per ottenere N = 1? Considerando che stiamo dividendo per due ad ogni passaggio, la risposta corretta è 4, che è il valore di log(16) base 2.

log(16) base 2

log(2^4) base 2

4 * log(2) base 2, poiché log(a) base a = 1

quindi, 4 * log(2) base 2 = 4

3. Ad ogni livello, il secondo termine della ricorrenza è considerato la radice.

Sebbene la parola 'albero' appaia nel nome di questa strategia, non è necessario essere un esperto di alberi per comprenderla.

Come utilizzare un albero di ricorsione per risolvere le relazioni di ricorrenza?

Il costo del sottoproblema nella tecnica dell'albero di ricorsione è la quantità di tempo necessaria per risolvere il sottoproblema. Pertanto, se noti la frase 'costo' collegata all'albero di ricorsione, si riferisce semplicemente alla quantità di tempo necessaria per risolvere un determinato sottoproblema.

Capiamo tutti questi passaggi con alcuni esempi.

Esempio

Considera la relazione di ricorrenza,

T(n) = 2T(n/2) + K

Soluzione

La relazione di ricorrenza data mostra le seguenti proprietà,

Un problema di dimensione n è diviso in due sottoproblemi ciascuno di dimensione n/2. Il costo per combinare le soluzioni di questi sottoproblemi è K.

Ogni problema di dimensione n/2 è diviso in due sottoproblemi ciascuno di dimensione n/4 e così via.

All'ultimo livello, la dimensione del sottoproblema verrà ridotta a 1. In altre parole, raggiungiamo finalmente il caso base.

Seguiamo i passaggi per risolvere questa relazione di ricorrenza,

Passaggio 1: disegnare l'albero di ricorsione

Passaggio 2: calcolare l'altezza dell'albero

Poiché sappiamo che quando dividiamo continuamente un numero per 2, arriva un momento in cui questo numero si riduce a 1. Come per il problema di dimensione N, supponiamo che dopo K divisioni per 2, N diventi uguale a 1, il che implica, ( n/2^k) = 1

Qui n/2^k è la dimensione del problema all'ultimo livello ed è sempre uguale a 1.

Ora possiamo calcolare facilmente il valore di k dall'espressione precedente prendendo log() su entrambi i lati. Di seguito è riportata una derivazione più chiara,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) base 2

Quindi l'altezza dell'albero è log(n) base 2.

generici Java

Passaggio 3: calcolare il costo a ciascun livello

• Costo al Livello-0 = K, due sottoproblemi vengono uniti.
• Costo al Livello-1 = K + K = 2*K, due sottoproblemi vengono uniti due volte.
• Costo al Livello-2 = K + K + K + K = 4*K, due sottoproblemi vengono uniti quattro volte. e così via....

Passaggio 4: calcolare il numero di nodi a ciascun livello

Determiniamo innanzitutto il numero di nodi nell'ultimo livello. Dall'albero di ricorsione possiamo dedurre questo

• Il livello 0 ha 1 (2 ^ 0) nodo
• Il livello 1 ha 2 (2 ^ 1) nodi
• Il livello 2 ha 4 (2 ^ 2) nodi
• Il livello 3 ha 8 (2 ^ 3) nodi

Quindi il livello log(n) dovrebbe avere 2^(log(n)) nodi cioè n nodi.

Passaggio 5: riepiloga il costo di tutti i livelli

• Il costo totale può essere scritto come:
• Costo totale = Costo di tutti i livelli tranne l'ultimo livello + Costo dell'ultimo livello
• Costo totale = Costo per il livello-0 + Costo per il livello-1 + Costo per il livello-2 +.... + Costo per livello-log(n) + Costo per l'ultimo livello

Il costo dell'ultimo livello viene calcolato separatamente perché è il caso base e non viene eseguita alcuna fusione all'ultimo livello, quindi il costo per risolvere un singolo problema a questo livello è un valore costante. Prendiamolo come O (1).

Inseriamo i valori nelle formule,

• T(n) = K + 2*K + 4*K + .... + log(n)` volte + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) volte)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) volte + O(n)

Se osservi attentamente l'espressione sopra, forma una progressione geometrica (a, ar, ar^2, ar^3... tempo infinito). La somma di GP è data da S(N) = a / (r - 1). Ecco il primo termine e r è il rapporto comune.