Ricorsione

La funzione ricorsiva è una funzione che chiama se stessa con un sottoproblema del problema originale.

Una funzione ricorsiva deve avere dei casi base, ovvero casi in cui la funzione restituisce un risultato senza chiamare se stessa, e dei casi non base in cui la funzione chiama se stessa con un sottoproblema più vicino ai casi base.

f(n) = \begin{equation}\begin{cases}1 & \mbox{se } n=1\\ n\cdot f(n-1) & \mbox{altrimenti}\end{cases}\end{equation}

$n-1$ è la dimensione del sottoproblema su cui viene invocata la ricorsione.

Questo esempio rappresenta il fattoriale:

fatt(n):
	if n == 1 then
		return 1
	else
		return n*fatt(n-1)

Come calcolare il costo computazionale

Per calcolare il costo computazionale, si calcola il numero di chiamate ricorsive per calcolare, in questo caso, il fattoriale.

Si può quindi scrivere $T(n)$ sfruttando la natura ricorsiva della funzione: T(n) = \begin{equation}\begin{cases}1 & \mbox{se } n=1\\ 1\cdot T(n-1) & \mbox{altrimenti}\end{cases}\end{equation}

Questa prende il nome di equazione di ricorrenza.

Si ha quindi \begin{align}T(n) & = 1+T(n-1) \\ &= 1+1+T(n-2) = 2+T(n-2)\\&=2+1+T(n-3) = 3+T(n-3) \\ &= \mbox{...} \\ &= i+T(n-i) \\ &= (n-1)+T(n-(n-1)) = n-1+T(1)=n-1+1 = n\end{align}

Quindi $T(n)=n\in \Theta (n)$. $\Theta ()$ perché è esattamente quella funzione studiata, e non si può scappare.

title: Attenzione!
Il costo però non è lineare, ma ESPONENZIALE! Perché? Perché l'input non è n, ma $\log n$, che è quanto serve per rappresentare il numero. Quindi la relazione tra $n$ e $\log n$ è esponenziale.

Un altro esempio potrebbe essere quello della serie di Fibonacci.

Massimo comun divisore

L’algoritmo di Euclide per implementare il Massimo comun divisore si implementa in questo modo:

$$MCD(m,n)=\begin{array}{c}\{\begin{array}{ll}m& \text{mbox}sem=n\\ MCD(m-n,n)& \text{mbox}sem>n\\ MCD(m,n-m)& \text{mbox}altrimenti\end{array}\end{array}$$

In pseudo codice può essere implementato in questa maniera:

MCD(m, n):
	if m == n then
		return m
	else if m > n then
		return MCD(m - n, n)
	else
		return MCD(m, n - m)

Il caso peggiore si verifica quando uno dei due numeri è 1.

$$T(m,n)\le T(\max \{m,n\},1)=\begin{array}{c}\{\begin{array}{ll}1& \text{mbox}se\max \{m,n\}=1\\ 1+T(\max \{m,n\}-1)& \text{mbox}altrimenti\end{array}\end{array}$$

Quindi $T(m,n)\in \Theta (\max \{m,n\})$.

Equazioni di ricorrenza

Le equazioni di ricorrenza sono usate per trovare le formule chiuse. Tra le equazioni di ricorrenza ci sono:

• Metodo iterativo
• Master theorem
• Metodo di sostituzione

Per determinare l’equazione di ricorrenza di una funzione ricorsiva, si deve:

• Determinare la dimensione dell’input $n$
• Determinare il caso base ($n_0$)
• Determinare il costo del caso base $b(n)$
• Determinare il costo del lavoro extra ricorsione $g(n)$

asd_10