Algoritmi e programmazione/La ricorsione

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 5. La ricorsione.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/La ricorsione}}/Grafi e alberi{{#ifcategory:Traduzioni\|/La ricorsione\|\|/La ricorsione}}\|4. Grafi e alberi]]	[[{{#ifcategory:Traduzioni\|/La ricorsione\|Algoritmi e programmazione\|/La ricorsione}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/La ricorsione}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/La ricorsione}}/Il paradigma "divide et impera"{{#ifcategory:Traduzioni\|/La ricorsione\|\|/La ricorsione}}\|6. Il paradigma "divide et impera"]]

2 ricorsione diretta: nella definizione di una procedura si richiama la procedura stessa
ricorsione indiretta: nella definizione di una procedura si richiama una o più procedure che richiamano la procedura stessa

4 Si rompe ricorsivamente un problema in analoghi sottoproblemi più semplici, fino a quando non si arriva alla soluzione di un problema elementare: 6. Il paradigma "divide et impera".

5 Non è una definizione circolare (all'infinito), ma c'è la condizione di terminazione (ricorsione finita).

Esempi[modifica | modifica sorgente]

Fattoriale[modifica | modifica sorgente]

6 La definizione stessa di fattoriale è di tipo ricorsivo.

7 A ogni passo si genera un unico sottoproblema anziché due → non sarà un albero binario completo.

Numeri di Fibonacci[modifica | modifica sorgente]

8 Un numero di Fibonacci FIB_{n + 1} è la somma dei due che lo precedono nell'ordinamento: FIB_{n − 1} e FIB_n.

9 La ratio aurea è il rapporto tra un segmento maggiore <math>a</math> e uno minore <math>b</math>: <math>\varphi = \tfrac{a}{b}</math>. Il segmento maggiore <math>a</math> è il medio proporzionale tra il minore <math>b</math> e la somma dei due:

<math>\left( a + b \right) : a = a : b ; \; \frac{ \varphi + 1 } {\varphi} = \varphi; \; {\varphi}^2 - \varphi - 1 = 0; \; \varphi = \frac{1 + \sqrt{5}}{2} \vee \varphi ' = \frac{1 - \sqrt{5}}{2}</math>

10 Ogni numero di Fibonacci ha la seguente relazione con la ratio aurea <math>\varphi</math>:

FIB_n = <math>\frac{{\varphi}^n - {\varphi'}^n}{\sqrt{5}}</math>

11 La ricorsione non procede in modo parallelo per livelli dell'albero, ma è un'analisi in profondità dell'albero della ricorsione, ovvero si segue ogni cammino fino alla foglia = soluzione elementare.

Algoritmo di Euclide[modifica | modifica sorgente]

12 Dati m e n, permette di calcolare il Massimo Comun Divisore:

se m > n → MCD(m, n) = MCD(n, m mod n)
condizione di terminazione: se n = 0 ritorna m

Valutazione di espressione in forma prefissa[modifica | modifica sorgente]

Per approfondire, vedi la pagina Notazione polacca su Wikipedia.

14 Ponendo per semplicità di trattare solo con operandi di somma e prodotto di arità 2, una espressione può essere definita ricorsivamente in funzione di se stessa: , con condizione di terminazione: l'espressione è uno degli operandi.

17 Inserendo l'espressione in un vettore , a ogni passo si valuta a[i]:

se a[i] è un operatore, valuta l'espressione a destra dell'operatore;
condizione di terminazione: se a[i] è un numero, ritornalo.

Ricerca binaria[modifica | modifica sorgente]

25 Si considera a ogni passo della ricorsione un sottovettore di metà dimensione, anch'esso ordinato.

Ricerca del massimo di un vettore[modifica | modifica sorgente]

27 A ogni passo, si suddivide il vettore in due sottovettori, si recupera il massimo di ciascun sottovettore, e si confrontano i risultati. Si termina quando il sottovettore ha un solo elemento.

Moltiplicazione rapida di 2 interi[modifica | modifica sorgente]

40 1º modo) Seguo la definizione ricorsiva: <math>\begin{cases} x \cdot y = x + x \cdot \left( y - 1 \right) \\ x \cdot 1 = x \end{cases}</math>

2º modo) Si assume:

si sa calcolare il prodotto solo di cifre decimali (come se si avessero solo le tavole pitagoriche);
per semplicità che x e y abbiano x = 2^k cifre.

Si divide x in due sottovettori x_s e x_d di metà dimensione, e così pure y in y_s e y_d → <math>\begin{cases} x = x_s \cdot {10}^Template:N \over 2 + x_d \\ y = y_s \cdot {10}^Template:N \over 2 + y_d \end{cases}</math>

<math>x \cdot y = \left( x_s \cdot {10}^Template:N \over 2 + x_d \right) \cdot \left( y_s \cdot {10}^Template:N \over 2 + y_d \right) = x_s \cdot y_s \cdot {10}^n + x_s \cdot y_d \cdot {10}^Template:N \over 2 + x_d \cdot y_s \cdot {10}^Template:N \over 2 + x_d \cdot y_d</math>

Si continua a suddividere ciascun sottovettore fino alla condizione di terminazione: i fattori hanno una sola cifra.

49 A ogni passo, si generano 4 sottoproblemi di dimensione metà → si richiama per 4 volte l'operazione di moltiplicazione.

Moltiplicazione rapida di 2 interi ottimizzata[modifica | modifica sorgente]

50 Il numero di moltiplicazioni richiamate a ogni passo si riduce a 3:

<math>x_s \cdot y_d+x_d \cdot y_s=x_s \cdot y_s+x_d \cdot y_d- \left( x_s-x_d \right) \cdot \left( y_s-y_d \right)</math>

Liste[modifica | modifica sorgente]

Definizioni[modifica | modifica sorgente]

52 sequenza lineare = insieme finito di elementi, ciascuno associato a un indice univoco, in cui conta la posizione reciproca tra di essi (cioè ogni elemento ha un successore e un predecessore).

53 accesso diretto: (implementazione tramite vettore) locazioni di memoria contigue accessibili tramite indice → complessità <math>O \left( 1 \right)</math>;
54 accesso sequenziale: l'accesso a un certo elemento necessita della scansione sequenziale della lista a partire dal primo elemento → complessità <math>O \left( n \right)</math>.

Una lista è una sequenza lineare ad accesso sequenziale. La lista è un concetto astratto, e si può implementare in C:

tramite un vettore: lo posso usare anche per dati in locazioni di memoria non contigue;
tramite un sistema a puntatori : in questo caso la lista si dice concatenata.

55 lista concatenata = insieme di elementi dello stesso tipo (dati), memorizzati in modo non contiguo (nodi, implementati tramite struct), accessibili mediante riferimento (link → puntatori) al successore/precedente. La memoria viene allocata e liberata dinamicamente per ogni nodo (→ i dati possono teoricamente essere infiniti), ma l'accesso non è diretto.

Classificazione[modifica | modifica sorgente]

56 ordinata / non ordinata
circolare / con testa e coda
singolo-linkata / doppio-linkata (senza/con link a successore)

Ricorsione[modifica | modifica sorgente]

51 Definizione ricorsiva: Una lista è un elemento seguito da una lista. Funzioni:

conteggio: a ogni passo: 1 + numero degli elementi della sottolista considerata a partire dal successore;
attraversamento: elenca gli elementi in una lista con una strategia (ordine) predefinita di percorrimento;
eliminazione di un elemento.

52 Non sempre la soluzione ricorsiva è più efficiente di quella iterativa.