Algoritmi/La ricorsione

Indice del libro
  • 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: Human-edit-redo.svg 6. Il paradigma "divide et impera".

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

EsempiModifica

FattorialeModifica

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 FibonacciModifica

Un numero di Fibonacci FIBn + 1 è la somma dei due che lo precedono nell'ordinamento: FIBn − 1 e FIBn.

La ratio aurea è il rapporto tra un segmento maggiore   e uno minore  :  . Il segmento maggiore   è il medio proporzionale tra il minore   e la somma dei due:

 

Ogni numero di Fibonacci ha la seguente relazione con la ratio aurea  :

FIBn =  

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 EuclideModifica

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 prefissaModifica

  Per approfondire su Wikipedia, vedi la voce Notazione polacca.

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 binariaModifica

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

Ricerca del massimo di un vettoreModifica

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 interiModifica

1º modo) Seguo la definizione ricorsiva:  

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 = 2k cifre.

Si divide x in due sottovettori xs e xd di metà dimensione, e così pure y in ys e yd 

 

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 ottimizzataModifica

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

 

ListeModifica

DefinizioniModifica

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

  1. accesso diretto: (implementazione tramite vettore) locazioni di memoria contigue accessibili tramite indice → complessità  ;
  2. accesso sequenziale: l'accesso a un certo elemento necessita della scansione sequenziale della lista a partire dal primo elemento → complessità  .

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.

ClassificazioneModifica

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

RicorsioneModifica

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.