DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

La RicorsioneLa Ricorsione

Marco D. Santambrogio – marco.santambrogio@polimi.itVer. aggiornata al 21 Maggio 2014

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

ObiettiviObiettivi

• La ricorsione

Ricordate la sigla GNUGNU = GNU is Not Unix

GNU = GNU is Not Unix GNU = GNU is Not Unix

GNU = GNU is Not GNU = GNU

2

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

La ricorsione: che cos’è?La ricorsione: che cos’è?

• Ricorsione indiretta: Un sottoprogramma P chiama un

sottoprogramma Q Q a sua volta chiama un terzo R, … R chiama nuovamente P

• Ricorsione diretta Un sottoprogramma P chiama se

stesso durante la propria esecuzione

3

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Un esempio classicoUn esempio classico

• Individuare, in un gruppo di palline l’unica pallina di peso maggiore delle altre facendo uso di una bilancia “a basculla”

• Per semplicità: il numero di palline sia una potenza di 3

• Algoritmo Pesate:• Se il gruppo di palline consiste in una sola pallina,

allora essa è banalmente la pallina cercata, altrimenti procedi come segue.

– Dividi il gruppo di palline in tre e confronta due dei tre sottogruppi.

– Se i due gruppi risultano di peso uguale scarta entrambi, altrimenti scarta il gruppo non pesato e quello risultato di peso minore.

– Applica l’algoritmo Pesate al gruppo rimanente.

4

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Altri esempi di ricorsioneAltri esempi di ricorsione

• La sommatoria di una sequenza di numeri

• Fattoriale:

• In arte e non solo…

5

Fact(n)=n*Fact(n-1)Fact(0)=1

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Scopo della programmazione Scopo della programmazione ricorsivaricorsiva

• Lo scopo è quelo di risolvere un problema facendo riferimento allo stesso problma su scala ridotta

• La condizione di terminazione avviene quando si identifica uno o più casi semplici con soluzione immediata

• La struttura di un algoritmo ricorsivo è il seguente

if (è il caso semplice)risolvilo

elseusa la ricorsione su dati ridotti

6

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Il calcolo del fattorialeIl calcolo del fattoriale

In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi minori o uguali di quel numero

7

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Il main del fattorialeIl main del fattoriale

8

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Il fattoriale iterativoIl fattoriale iterativo

9

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

n = 3 main

fat= FattRic(3)

fat= FattRic(2)

fat= FattRic(1)

fat= FattRic(0)

La ricorsione come strumentoLa ricorsione come strumentodi programmazionedi programmazione

Calcolo del Fattoriale in modo ricorsivo:

1

1

2

6

Fact(n)=n*Fact(n-1)Fact(0)=1

10

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

MoltiplicazioneMoltiplicazione

• Ideare un procedimento ricorsivo per calcolare il prodotto di due interi

• Nota: A*1=A; A*B = A + A*(B-1)

int MulRic(int a, int b){int ris;if (b == 1) ris = a;else ris = a + MulRic(a ,b–1);return ris;

}

11

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Successione di FibonacciSuccessione di Fibonacci

“Quante coppie di conigli si ottengono dopo N mesi (salvo i casi di morte) supponendo che ogni coppia dia alla luce un‘altra coppia ogni mese e che le coppie più giovani siano in grado di riprodursi già al secondo mese di vita?”

12

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Successione di FibonacciSuccessione di Fibonacci

• Fib(n)=Fib(n-1)+Fib(n-2)• Fib(0)=0; Fib(1)=1;

int fibRic (int n) {

int ris;

if (n == 0) ris = 0;

else if (n == 1) ris = 1;

else ris = fibRic(n–1) + fibRic(n–2);

return ris;

}

13

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Un problema interessante: La torre di BrahmaUn problema interessante: La torre di Brahma

14

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

La leggendaLa leggenda

• Narra la leggenda che all'inizio dei tempi, Brahma portò nel grande tempio di Benares, sotto la cupola d'oro che si trova al centro del mondo, tre colonnine di diamante e sessantaquattro dischi d'oro, collocati su una di queste colonnine in ordine decrescente, dal più piccolo in alto, al più grande in basso.

• E' la sacra Torre di Brahma che vede impegnati, giorno e notte, i sacerdoti del tempio nel trasferimento della torre di dischi dalla prima alla terza colonnina.

• Essi non devono contravvenire alle regole precise, imposte da Brahma stesso, che richiedono di spostare soltanto un disco alla volta e che non ci sia mai un disco sopra uno più piccolo.

• Quando i sacerdoti avranno completato il loro lavoro e tutti Quando i sacerdoti avranno completato il loro lavoro e tutti i dischi saranno riordinati sulla terza colonnina, la torre e il i dischi saranno riordinati sulla terza colonnina, la torre e il tempio crolleranno e sarà la fine del mondo. tempio crolleranno e sarà la fine del mondo.

15

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Il giocoIl gioco

16

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

LL’’ideaidea

• Se voglio spostare n anelli dal piolo sorgente, a quello destinazione, usando come appoggio il piolo ausiliario, devo prima spostare n - 1 anelli dal sorgente all'ausiliario, usando come appoggio il piolo destinazione; poi sposto l'unico anello rimasto dal sorgente al piolo destinazione; infine sposto gli n - 1 anelli che si trovano sull'ausilliario all'anello destinazione.

• Quando si spostano gli n - 1 anelli la funzione hanoi richiama se stessa, cioè effettua una chiamata ricorsiva, semplificando però il problema perché bisogna spostare un numero di anelli inferiore.

• In pratica, con la ricorsione il problema viene continuamente ridotto di complessità fino alla soluzione banale in cui rimane solo un anello, che viene semplicemente spostato nel piolo destinazione.

17

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

CodiceCodice

void hanoi(int n, int sorgente, int destinazione, int aux) {

if (n==1)

printf("Sposto da %d a %d.\n",sorgente, destinazione);

else{

hanoi(n - 1, sorgente, aux, destinazione);

hanoi(1, sorgente, destinazione, aux);

hanoi(n - 1, aux, destinazione, sorgente);

}

}

18

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Esercizio: Massimo di un Esercizio: Massimo di un arrayarray

• Ideare un procedimento ricorsivo per calcolare il massimo di un array di interi

• Idea: max(vect[0 : N]) =max(vect[0],max(vect[1 : N]))

int max(int *array, int n){int maxs;if (n==1) return array[0]; /*Caso Array 1 elemento*/if (n==2){ /*Caso Base*/ if (array[0]>array[1]) return array[0]; else return array[1];}maxs = max(&array[1],n-1); /*Risolvi Problema Ridotto*/if (array[0]>maxs)return array[0];else return maxs;

}

19

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Fonti per lo studio + Fonti per lo studio + CreditsCredits• Fonti per lo studio

Introduzione alla programmazione in MATLAB, A.Campi, E.Di Nitto, D.Loiacono, A.Morzenti, P.Spoletini, Ed.Esculapio

• Capitolo 4– Particolare attenzione al 4.5

• Credits Prof. A. Morzenti Gianluca Palermo

20