tecnica di programmazione che permette di esprimere in maniera naturale algoritmi ricorsivi

(1)

Ricorsione

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova

Ricorsione, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.1/25

Ricorsione

tecnica di programmazione che permette di esprimere in maniera naturale algoritmi ricorsivi

un algoritmo A è ricorsivo se può essere rappresentato dalle seguenti relazioni:

(1) A( ¯ d 0 ) = ¯ s 0

(2) A( ¯ d) = F (A( ¯ d ⁰ )) dove

d, ¯d ¯ ⁰ e ¯ d 0 sono tre insiemi di dati con ¯ d 6= ¯ d 0 e d ¯ ⁰ “più semplice” di ¯ d

s ¯ 0 è la soluzione che si ottiene applicando A a ¯ d 0

1 è detta condizione di terminazione o caso base, mentre 2 è detta relazione di ricorrenza

Programmazione ricorsiva

metodo che richiama se stesso direttamente (ricorsione diretta) oppure attraverso altri metodi (ricorsione indiretta)

codifica

condizione di terminazione

relazione di ricorrenza in cui richiama se stesso (direttamente o indirettamente)

struttura iterativa

metodo più generale per i cicli

Fattoriale - I

definizione

0! = 1

n! = n(n − 1)!

metodo

int fact(int n) {

if (n==0) return 1;

else return n * fact(n-1);

}

(2)

Fattoriale - II

traccia di esecuzione fact(3)

--> n=3

3*fact(2) --> n=2

2*fact(1) --> n=1

1*fact(0) --> n=0

<-- 1

<-- 2

<-- 6

Fibonacci

numeri di Fibonacci

1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

definizione

Fib(1) = 1 Fib(2) = 1

Fib(n) = Fib(n − 1) + Fib(n − 2)

metodo

int fib(int n) { if (n<=2) return 1;

else return fib(n-1)+fib(n-2);

}

Stringa palindroma - I

la stringa s é palindroma se s=reverse(s)

definizione

Palin(s) = true se L(s) <= 1

Palin(s) = (s

1

= s

L(s)

) ∧ Palin(s

_2:L(s)−1

) se L(s) > 1

dove

s è una stringa

L(s) ⁰ è la lunghezza della stringa s

s _i è l’i-esimo carattere

è la sottostringa di s tra il j-esimo e m-esimo

Stringa palindroma - II

metodo

boolean palin(String st) { if(st.length()<=1) return true;

else

return(st.charAt(0)==st.charAt(st.length()-1))

&&

palin(st.substring(1,st.length()-1) );

}

(3)

Stringa palindroma - III

traccia di esecuzione per la stringa "radar"

palin("radar") --> st="radar"

’r’==’r’ && palin("ada") --> st="ada"

’a’==’a’ && palin("d") --> st="d"

<-- true

Stringa palindroma - IV

traccia di esecuzione per la stringa "alma"

palin("alma") --> st="alma"

’a’==’a’ && palin("lm") --> st="lm"

’l’==’m’ && palin("")

<-- false

Note di programmazione

attenzione alla codifica di

condizione di terminazione

deve essere presente con il test corretto

relazione di ricorrenza

deve ridurre la complessitá convergendo verso un caso base

Errori nella ricorsione - I

assenza della CDT int fact(int n) {

return n * fact(n-1);

}

boolean palin(String st) {

return(st.charAt(0)==st.charAt(st.length()-1))

&&

palin(st.substring(1,st.length()-1) );

}

(4)

Errori nella ricorsione - II

test errato nella CDT int fact(int n) {

if (n>0) return 1;

else return n * fact(n-1);

}

boolean palin(String st) { if(st.length()<0) return true;

else

return(st.charAt(0)==st.charAt(st.length()-1))

&&

palin(st.substring(1,st.length()-1) );

}

Errori nella ricorsione - III

non si converge nella RDR int fact(int n) {

if (n==0) return 1;

else return n * fact(n+1);

}

boolean palin(String st) { if(st.length()<=1) return true;

else

return(st.charAt(0)==st.charAt(st.length()-1))

&&

palin(st.substring(0,st.length()) );

}

Ricorsione vs Cicli

ricorsione ciclo

potenza espressiva + -

efficienza - +

eliminazione della ricorsione trasformare ricorsione in un ciclo

tail recursion

unica invocazione ricorsiva come ultima azione

Eliminazione della ricorsione

fattoriale

int fact(int n) { int f=1;

while (n>0) f=f*n--;

return f;

}

fibonacci

int fib( int n ) { int k, f, f1, f2;

f = f1 = f2 = 1;

for(k=2;k<n;k++) {

(5)

Zero di una funzione - I

definizione

zero(F , x 0 , x 1 ) = x 0

se |x 0 − x 1 | ≤ zero(F , x 0 , x 1 ) = zero(F , ^x

⁰

^+x ₂

¹

, x 1 )

se sign(F ( ^x

⁰

^+x ₂

¹

)) = sign(F (x 0 )) zero(F , x 0 , x 1 ) = zero(F , x 0 , ^x

⁰

^+x ₂

¹

)

altrimenti

Zero di una funzione - I

x

₂

x

₁

y

x y=f(x)

Zero di una funzione - II

metodo

double zero(double x1, double x2){

boolean x1Negativo;

double x;

x1Negativo=f(x1)<0;

if ((f(x2) <0) == x1Negativo) return Double.NEGATIVE_INFINITY;

else if (Math.abs(x1-x2)<EPS) return x1;

else {

x=(x1+x2)/2.0;

if ((f(x)<0) == x1Negativo) return zero(x,x2);

else return zero(x1,x);

} }

Torre di Hanoi - I

gioco apparso alla fine del XIX secolo

dati tre pioli ed una torre di dischi di diametro

decrescente presente in un piolo, spostare la torre su un altro piolo muovendo un solo disco alla volta e non avendo mai un disco più largo sopra uno più piccolo

| | |

---

1 2 3

(6)

Torre di Hanoi - II

definizione

Hanoi(1, k, l) = muovi un disco dal piolo k al piolo l Hanoi(n, k, l) = Hanoi(n − 1, k, t),

Hanoi(1, k, l), Hanoi(n − 1, t, l)

dove k, l, t ∈ {1, 2, 3} e k 6= l, l 6= t e k 6= t

Torre di Hanoi - III

Hanoi(3,1,3)

Hanoi(2,1,2)

• Hanoi(1,1,3)

• Hanoi(1,1,2)

• Hanoi(1,3,2)

Hanoi(1,1,3)

Hanoi(2,2,3)

• Hanoi(1,2,1)

• Hanoi(1,2,3)

• Hanoi(1,1,3)

Torre di Hanoi - IV

tempo di calcolo

quando i monaci del Tempio di Brama avranno finito di muovere una torre di 64 dischi d’oro il mondo terminerà

tecnica di programmazione che permette di esprimere in maniera naturale algoritmi ricorsivi

Ricorsione

Ricorsione

tecnica di programmazione che permette di esprimere in maniera naturale algoritmi ricorsivi

un algoritmo A è ricorsivo se può essere rappresentato dalle seguenti relazioni:

(1) A( ¯ d 0 ) = ¯ s 0

(2) A( ¯ d) = F (A( ¯ d 0 )) dove

 d, ¯d ¯ 0 e ¯ d 0 sono tre insiemi di dati con ¯ d 6= ¯ d 0 e d ¯ 0 “più semplice” di ¯ d

 s ¯ 0 è la soluzione che si ottiene applicando A a ¯ d 0

1 è detta condizione di terminazione o caso base, mentre 2 è detta relazione di ricorrenza

Programmazione ricorsiva

metodo che richiama se stesso direttamente (ricorsione diretta) oppure attraverso altri metodi (ricorsione indiretta)

codifica

 condizione di terminazione

 relazione di ricorrenza in cui richiama se stesso (direttamente o indirettamente)

struttura iterativa

metodo più generale per i cicli

Fattoriale - I

definizione

0! = 1

n! = n(n − 1)!

metodo

int fact(int n) {

if (n==0) return 1;

else return n * fact(n-1);

}

Fattoriale - II

traccia di esecuzione fact(3)

--> n=3

3*fact(2) --> n=2

2*fact(1) --> n=1

1*fact(0) --> n=0

<-- 1

<-- 1

<-- 2

<-- 6

Fibonacci

numeri di Fibonacci

1, 1, 2, 3, 5, 8, 13, 21, 34, . . .

definizione

Fib(1) = 1 Fib(2) = 1

Fib(n) = Fib(n − 1) + Fib(n − 2)

metodo

int fib(int n) { if (n<=2) return 1;

else return fib(n-1)+fib(n-2);

}

Stringa palindroma - I

la stringa s é palindroma se s=reverse(s)

definizione

Palin(s) = true se L(s) <= 1

Palin(s) = (s

= s

) ∧ Palin(s

) se L(s) > 1

dove

 s è una stringa

 L(s) 0 è la lunghezza della stringa s

 s i è l’i-esimo carattere

è la sottostringa di s tra il j-esimo e m-esimo

Stringa palindroma - II

metodo

boolean palin(String st) { if(st.length()<=1) return true;

else

return(st.charAt(0)==st.charAt(st.length()-1))

&&

palin(st.substring(1,st.length()-1) );

}

Stringa palindroma - III

traccia di esecuzione per la stringa "radar"

palin("radar") --> st="radar"

’r’==’r’ && palin("ada") --> st="ada"

’a’==’a’ && palin("d") --> st="d"

<-- true

<-- true

<-- true

Stringa palindroma - IV

traccia di esecuzione per la stringa "alma"

palin("alma") --> st="alma"

’a’==’a’ && palin("lm") --> st="lm"

’l’==’m’ && palin("")

(2) A( ¯ d) = F (A( ¯ d ⁰ )) dove

d, ¯d ¯ ⁰ e ¯ d 0 sono tre insiemi di dati con ¯ d 6= ¯ d 0 e d ¯ ⁰ “più semplice” di ¯ d

s ¯ 0 è la soluzione che si ottiene applicando A a ¯ d 0

condizione di terminazione

relazione di ricorrenza in cui richiama se stesso (direttamente o indirettamente)

s è una stringa

L(s) ⁰ è la lunghezza della stringa s

s _i è l’i-esimo carattere

condizione di terminazione

relazione di ricorrenza

tail recursion

se |x 0 − x 1 | ≤ zero(F , x 0 , x 1 ) = zero(F , ^x

^+x ₂

se sign(F ( ^x

^+x ₂

)) = sign(F (x 0 )) zero(F , x 0 , x 1 ) = zero(F , x 0 , ^x

^+x ₂