FANDOM


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

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

EsempiModifica

FattorialeModifica

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 FibonacciModifica

Fibonacci

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

9 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}

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

FIBn = \frac{{\varphi}^n - {\varphi'}^n}{\sqrt{5}}

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 EuclideModifica

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 prefissaModifica

Exquisite-kfindPer 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: Forma prefissa, con condizione di terminazione: l'espressione è uno degli operandi.

17 Inserendo l'espressione in un vettore Vettore forma prefissa, 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

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

Ricerca del massimo di un vettoreModifica

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 interiModifica

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

Si divide x in due sottovettori xs e xd di metà dimensione, e così pure y in ys e yd\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.

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 ottimizzataModifica

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

ListeModifica

DefinizioniModifica

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

  1. 53 accesso diretto: (implementazione tramite vettore) locazioni di memoria contigue accessibili tramite indice → complessità O \left( 1 \right);
  2. 54 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 Lista 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.

ClassificazioneModifica

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

RicorsioneModifica

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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale