Esempi di algoritmi ricorsivi PDF

Preview

Summary

Ottimi appunti per poter superare l'esame di programmazione 1...

Description

Esempi di algoritmi ricorsivi In questo modulo presentiamo alcuni algoritmi ricorsivi basati sia sull'approccio incrementale sia sull'approccio divide et impera analizzandoli in termini comparativi. Inoltre viene proposta la versione ricorsiva dell'algoritmo di Euclide per il calcolo del MCD tra due interi non negativi. Infine svilupperemo un algoritmo ricorsivo per il calcolo dell'n-esimo numeri di Fibonacci e ne analizzeremo la complessità. Function ricorsiva per la somma iterativa degli elementi di un array 1D Il primo problema che affrontiamo è il calcolo della somma degli elementi di un array 1D. Vogliamo sviluppare un algoritmo ricorsivo basato sull'idea incrementale. L'algoritmo incrementale per la somma può essere descritto, come già visto in precedenza, mediante la seguente formula ricorrente del primo ordine lineare a coefficienti non costanti :

Il coefficiente non costante a(k) indica il k-esimo elemento dell'array. Il valore della somma ad ogni passo è dato da quello precedente aumentato del valore dell'elemento corrente dell'array. La seguente function implementa il problema descritto:

Si osservi la solita struttura dell'algoritmo ricorsivo: è presente un costrutto if che consente di stabilire se l'istanza in esame è il caso base (in questo caso se l'array è costituito da un unico elemento) o meno; cioè se n>1 bisogna restituire la soluzione del problema come somma dell'n-esimo elemento dell'array più la somma dei primi

n-1 elementi dell'array descritta mediante una autoattivazione della stessa function passando come parametri ancora una volta l'array a ma come secondo argomento n1 cioè la lunghezza della porzione cui siamo interessati. La complessità di tempo di quest'algoritmo è n-1 somme : si tratta della stessa complessità di tempo dell'algoritmo iterativo, infatti è facile convincersi, che i due algoritmi, sono completamente equivalenti tra loro in quanto descrivono la stessa identica sequenza computazionale. Function ricorsiva per la somma “divide et impera” degli elementi di un array 1D Vogliamo ora risolvere lo stesso problema sviluppando un algoritmo ricorsivo basato sull'approccio divide et impera. Un simile algoritmo è rappresentato da quello di raddoppiamento per la somma dove, la soluzione del problema, è data dalla combinazione delle somme a coppie che si effettuano tra due porzioni dell'array, partendo dall'istanza più complessa fino a raggiungere quella banale. La function che implementa ricorsivamente l'algoritmo di raddoppiamento è la seguente:

Il caso base è rappresentato dalla situazione in cui la porzione è costituita da un unico elemento. Se non si è nel caso base, si effettua la suddivisione dell'array in due porzioni. La suddivisione viene descritta mediante la variabile “mediano” cui viene assegnato l'indice mediano della porzione in esame e dopodichè si restituisce la somma tra la somma che va da “primo” a “mediano”, più, la somma che va da “mediano+1” a “ultimo”. Naturalmente la somma di ognuna delle due porzioni è specificata mediante l'autoattivazione della stessa function. La complessità di tempo, ancora una volta, è identica a quella dello stesso algoritmo

non ricorsivo e cioè in questo caso pari a n-1 somme. Function ricorsiva per la determinazione iterativa del massimo di un array Affrontiamo ora il problema della determinazione del massimo elemento di un array 1D. Per prima cosa sviluppiamo un algoritmo ricorsivo basato sull'idea incrementale. La determinazione dell'elemento massimo è un operazione descrivibile dalla seguente formula ricorrente:

Semplicemente si stabilisce che il massimo tra i primi k elementi di un array si ottiene calcolando il massimo tra il k-esimo elemento dell'array a(k) e il massimo tra i precedenti k-1 elementi. Si noti la condizione iniziale che dichiara come primo valore del massimo il primo elemento dell'array. Data la formula ricorrente è ora molto facile determinare il seguente algoritmo:

Ancora una volta si noti la completa equivalenza tra questo algoritmo e la sua versione non ricorsiva : le complessità di tempo coincidono. Function ricorsiva per la determinazione “divide et impera” del massimo di un array L'algoritmo precedente può essere implementato adottando l'approccio divide et impera. Uno schema può essere utile per meglio chiarire quale sarà la strategia che adopereremo.

In pieno stile divide et impera la determinazione del massimo è effettuata operando le consuete suddivisioni dell'array in porzioni che sono caratteristiche degli algoritmi di raddoppiamento. Ed ecco la function che corrisponde a quanto cercato:

Classica struttura dell'algoritmo ricorsivo. Se “primo“ è uguale ad “ultimo” siamo nel caso banale cioè l'array è costituito da un unico elemento che è proprio il massimo cercato. Nel caso contrario l'array va suddiviso attraverso la variabile “mediano” e viene restituito il massimo (calcolato dalla function max) tra due numeri: la soluzione del problema per la porzione che va da “primo” a “mediano” e la soluzione del problema per la porzione che va da “mediano+1” a “ultimo”. La soluzione delle due istanze viene espressa al solito, mediante autoattivazione della stessa function. La complessità di tempo di quest'algoritmo è la stessa complessità trovata per l'algoritmo di raddoppiamento per il massimo cioè n-2 confronti.

Algoritmo ricorsivo di Euclide per il calcolo del MCD La tecnica di programmazione ricorsiva si applica anche ad algoritmi che non rientrano nei due paradigmi dell'approccio iterativo e dell'approccio divide et impera. La slide ripropone l'algoritmo di Euclide per il calcolo del MCD.

Il ciclo while viene effettuato se il modulo, cioè il resto della divisione intera, tra “a” e “b” è diverso da zero. Se il modulo che abbiamo chiamato “r”, è diverso da zero, allora la successiva iterazione calcola il modulo tra “b” ed “r”. Se invece il modulo tra il valore di “a” e il valore di “b” risulta essere uguale a zero il valore di “b” è il MCD cercato. Presentiamo ora la versione ricorsiva di quest'algoritmo:

Il costrutto if permette di stabilire ancora una volta se si è in presenza del caso base. Il caso base, in quest'algoritmo, è rappresentato dalla situazione in cui “r” è uguale a zero e di conseguenza bisogna restituire immediatamente la soluzione. Se non si è nel caso base, la function si autoattiva per risolvere un'istanza più semplice che coinvolge “b” ed “r”.

Nella chiamata l'argomento “b” corrisponde al parametro “a” nell'intestazione, l'argomento di chiamata “r” corrisponde al parametro “b” nell'intestazione. Algoritmo ricorsivo elementare di Fibonacci Affrontiamo ora il problema del calcolo dell'n-esimo numeri di Fibonacci. L'algoritmo iterativo che risolve questo problema è già stato presentato nei capitoli precedenti e aveva complessità di tempo pari a n-1 somme. Quella che presentiamo è invece la versione ricorsiva dell'algoritmo già visto:

L'algoritmo si presenta nella versione che chiameremo elementare. Si osservi la solita struttura dell'algoritmo ricorsivo: c'è un caso base che coincide proprio con le condizioni iniziali della formula ricorrente e se non si rientra nel caso base cioè se n>1 allora bisogna restituire la somma dei due numeri di fibonacci precedenti che vengono descritti mediante autoattivazione della stessa function con argomento n-1 la prima volta n-2 la seconda volta. Si noti anche la diretta consequenzialità tra la formula ricorrente, le sue condizioni iniziali e il caso base e il caso non base nella implementazione ricorsiva. La determinazione della complessità di tempo di quest'algoritmo va determinata operando opportune considerazioni.

Nella figura sopra riportata abbiamo voluto descrivere, schematicamente, la sequenza di autoattivazioni generata dall'invocazione della fucntion fib_ric_el con argomento di chiamata n=5. Va osservato un fatto fondamentale. Nelle porzioni cerchiate in rosso vengono calcolate quantità che sono di fatto, già calcolate a sinistra del nostro albero delle autoattivazioni. Lo stesso dicasi per il secondo numero di Fibonacci ma esistono tre autoattivazioni di Fib(2): due di queste sono inutili perchè ricalcolano un numero che era già stato determinato. Per inciso il valore del quinto numero di Fibonacci è 5. Questo numero 5 si ottiene andando a sommare i valori che in figura, sono evidenziati con un riquadro di colore verde. Insomma nelle foglie di quest'albero appare 5 volte il calcolo del primo numero di Fibonacci che è pari a 1. Quindi si può concludere che l'intera struttura ad albero delle autoattivazioni rimanendo, di fatto, in parte inutilizzata. Possiamo dunque dare risposta al quesito iniziale sulla complessità di tempo dell'algoritmo ricorsivo elementare di Fibonacci. Dal momento che, il valore dell'n-esimo numero di Fibonacci f(n) viene calcolato dalla function fib_ric_el sommando un numero opportuno di volte la costante 1 e che questa operazione viene iterata per f(n) volte la risposta è la seguente: la complessità di tempo dell'algoritmo ricorsivo elementare di Fibonacci è pari a: f(n)-1 somme dove f(n) è circa pari al numero di Phidia (rapporto aureo). Volendo esplicitare il numero di Phidia otteniamo che:

Ossia, la complessità di tempo dell'algoritmo ricorsivo elementare di Fibonacci è dell'ordine di 1.618^n, che è una classe di complessità computazionale esponenziale. In definitiva si può concludere che l'algoritmo in questione è un pessimo algoritmo in quanto per n arbitrariamente grande si otterrebbero tempi di computo irragionevoli. In questo caso le complessità di tempo della versione iterativa e quella ricorsiva dell'algoritmo per il calcolo dell'n-esimo numero di Fibonacci NON sono uguali....