# Algoritmi/La ricorsione

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
* 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
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".
Non è una definizione circolare (all'infinito), ma c'è la condizione di terminazione (ricorsione finita).

## Esempi
### Fattoriale

La definizione stessa di fattoriale è di tipo ricorsivo.
A ogni passo si genera un unico sottoproblema anziché due → non sarà un albero binario completo.

### Numeri di Fibonacci

Un numero di Fibonacci FIB$_{n+1}$ è la somma dei due che lo precedono nell'ordinamento: FIB$_{n−1}$ e FIB$_n$.
La ratio aurea è il rapporto tra un segmento maggiore $a$ e uno minore $b$: $\varphi ={\tfrac {a}{b}}$. Il segmento maggiore $a$ è il medio proporzionale tra il minore $b$ e la somma dei due:
    $\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}}$
Ogni numero di Fibonacci ha la seguente relazione con la ratio aurea $\varphi$:
    FIB$_n$ = ${\frac {{\varphi }^{n}-{\varphi '}^{n}}{\sqrt {5}}}$
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

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

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.
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

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

### Ricerca del massimo di un vettore

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

1º modo) Seguo la definizione ricorsiva: ${\begin{cases}x\cdot y=x+x\cdot \left(y-1\right)\\x\cdot 1=x\end{cases}}$
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$ → ${\begin{cases}x=x_{s}\cdot {10}^{n \over 2}+x_{d}\\y=y_{s}\cdot {10}^{n \over 2}+y_{d}\end{cases}}$
    $x\cdot y=\left(x_{s}\cdot {10}^{n \over 2}+x_{d}\right)\cdot \left(y_{s}\cdot {10}^{n \over 2}+y_{d}\right)=x_{s}\cdot y_{s}\cdot {10}^{n}+x_{s}\cdot y_{d}\cdot {10}^{n \over 2}+x_{d}\cdot y_{s}\cdot {10}^{n \over 2}+x_{d}\cdot y_{d}$
Si continua a suddividere ciascun sottovettore fino alla condizione di terminazione: i fattori hanno una sola cifra.
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

Il numero di moltiplicazioni richiamate a ogni passo si riduce a 3:
    $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)$

## Liste
### Definizioni

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).
* accesso diretto: (implementazione tramite vettore) locazioni di memoria contigue accessibili tramite indice → complessità $O\left(1\right)$;
* accesso sequenziale: l'accesso a un certo elemento necessita della scansione sequenziale della lista a partire dal primo elemento → complessità $O\left(n\right)$.
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.
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

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

### Ricorsione

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.
Non sempre la soluzione ricorsiva è più efficiente di quella iterativa.