Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 6.Ricorsione lineare


Dimostrazione per induzione

Il calcolo della potenza enne-ma di un dato numero.

Il calcolo della potenza enne-ma di un dato numero.


Codice della funzione PotenzaN

Si presume che siano stati assegnati Xre, numero che si vuole elevare a potenza e N potenza alla quale si vuole elevare Xre.
SI noti che l’algoritmo è simile a quello per il calcolo della somma dei Numeri interi fatto salvo per il caso base che vale 1, infatti (Xre)0=1.

double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}

Di seguito si mostra sia lo stack dei processi che la modifica dei parametri man mano che il processo avanza. L’esempio è fatto per Xre=0.9 e N=6

PotenzaN(0.9,3)


Esercizio

Scrivere un algoritmo ricorsivo per determinare se un assegnato numero intero positivo N è primo.

Si dimostra che un numero è primo se nell’intervallo 1..√N  non ha divisori tranne il numero 1.

Esercizio (segue)

Scrivere un algoritmo ricorsivo per determinare se un assegnato numero intero positivo N è primo.

int main(){
int N, radN;
cout<<"Inserisci un numero intero: "; cin>>N;
radN=sqrt(N);
if (primo(N, sqrt(N))
cout<<" Il numero "<<N<<" e' primo "<<endl;
else
cout<<" Il numero "
<<N<<" non e' primo "<<endl;
system("PAUSE");
}

Esercizio (segue)

bool primo(int n, int kn)
{ // ricerca eventuali divisori di kn nell'intervallo 2-sqrt(kn)

if (kn<2) // Caso base: non ha trovato alcun divisore di kn
return true;
else
if (n%kn==0)
// Esiste almeno un divisore di kn diverso da 1
return false;
else
return primo(n,kn-1); // Chiamata ricorsiva su un valore di kn minore
}

Numeri primi.

Esercizio (segue)

Scrivere un algoritmo ricorsivo per determinare quanti numeri primi ci sono in un preassegnato intervallo K1..K2 di numeri interi positivi.

Numeri Primi Intervallo.

Algoritmo di Euclide per il calcolo del massimo comun divisore

(300 A.C.)
Siano m ed n due numeri naturali e supponiamo sia m>n

  1. Si divide m per n
  2. Se il resto è zero allora n è il MCD tra m e n.
  3. Se il resto è diverso da zero torna al primo passo scambiando m con n e n con r (cioè dividi n per r).

Algoritmo di Euclide

Di seguito è mostrata una interpretazione geometrica dell’algoritmo di Euclide.
Si vuole il MCD dei numeri M e N rappresentati ciascuno da un segmento di lunghezza M e N.
Il segmento restante dalla differenza tra M e N, detto R viene successivcamente confrontato con N che quindi assume il ruole di M nel caso precedente.
Si prosegue fin quando I due segmenti che si confrontano non hanno la stessa lunghezza. Il valore ultimo di R sarà il MCD tra M e N.

Algoritmo di Euclide


Algoritmo di Euclide (segue)

Un algoritmo ricorsivo per il calcolo del MCD tra M e N può essere il seguente:

Pseudo codice
IF M o N sono valori che rappresentano una soluzione valida
MCD ← valore della soluzione (M o N)

ELSE
MCD ← MCD(N, M MOD N)

In figura si mostrano le versioni iterativa e ricorsiva per il calcolo del MCD secondo l’algoritmo di Euclide.


Algoritmo di Euclide (segue)

Di seguito viene mostrato un esempio di calcolo del MCD, tra 30 e 18, secondo Euclide, con un algoritmo ricorsivo, tramite la rappresentazione in termini di processi aperti, variazioni del valore delle variabile durante il calcolo, rappresentazione geometrica.

MCD(int m, n)


Dimostrazione per induzione della correttezza dell’algortimo ricorsivo per il MCD

caso base
Poniamo MCD(M,0)=M

passo induttivo
Dobbiamo ora dimostrare che MCD(M’,N’)=MCD(N, M MOD N)

Supponiamo MCD(M’,N’)=X
allora M’=hX e N’=zX    dove h e z sono interi

essendo N’=M MOD N    questo implica per definizione che

M=kN+N’      dove k è un intero

ma N’=zX

allora M=kN+zX    inoltre N=M’=hX quindi

M=khX+zX=(kh+z)X=wX

essendo allora sia M che N divisibili per X questo è il MCD(M,N).

Altri esempi

Supponiamo di avere 3 lettere a b c. Vogliamo sapere quante permutazioni si possono fare con questi 3 caratteri.

- ci sono 3 maniere per scegliere quale lettera mettere in terza posizione (genericamente n)
abc acb cba

- per ognuna delle 3 scelte precedenti ci sono 2 maniere diverse per scegliere la lettere da mettere in seconda posizione in totale 3*2 (genericamente n*(n-1))
abc bac
acb cab
cba bca

- per ognuna delle 6 scelte precedenti c’è 1 sola maniera per scegliere la lettere da mettere in prima posizione in totale 3*2*1 (genericamente n*(n-1)…..*1)
abc bac
acb cab
cba bca

Altri esempi

Si definisce FATTORIALE di un numero N il prodotto di tutti i numeri da 0 a N come di seguito definito:

0!=1
N!=N*(N-1)*(N-2)*…….*(2)*1

Algoritmi e relativi codici iterativi e ricorsivi

double fattorialeIterativo(int Num)
{
int fatt=1;
for (int j=1;j<=Num;j++)
fatt=j*fatt;
return fatt;
}
double fattorialeRicorsivo(int Num)
{
if (Num==0)
return 1;
else
return Num*fattoriale(Num-1);
}

fattoriale ricorsivo

Algoritmi ricorsivi

Un algoritmo ricorsivo deve essere completo, deve cioè sempre esistere una soluzione qualunque sia l’input.
La completezza dipende dal dominio su cui si definisce l’algoritmo.
Esempio:
PotenzaN se definito sugli interi non è completo perché non funziona per gli interi negativi (infatti N-1 per N negativo non raggiunge mai lo 0).
Diventa completo se il domino di definizione è quello dei numeri interi positivi.
double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}

Algoritmi ricorsivi

Dall’esempio precedente si ricava che nel caso di cattiva definizione dell’algoritmo ricorsivo sia in termini di caso base che di chiamata ricorsiva si genera uno Stack Infinito.
Ciò accade quando non si raggiunge mai il caso base.

Infatti nel caso dell’algoritmo per il calcolo delle potenze di N se N è negativo sottraendo ad esso 1 ad ogni chiamata ricorsiva non raggiugeremmo mai il caso base previsto per N=0.

double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}

I materiali di supporto della lezione

fattoriale ricorsivo

numeri primi

numeri primi intervallo

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion