Paolo Bison

(1)

Ricorsione

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

Ricorsione, Paolo Bison, FI08, 2008-09-29 – p.1

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

₀

_{) = ¯s}

₀

(2) A _{( ¯} _d _{) =} F ₍ A _{( ¯} _d

^′

₎₎

dove

d ¯ , d ¯

^′

e d ¯

₀

sono tre insiemi di dati con d ¯ 6= ¯ d

₀

e

d ¯

^′

“più semplice” di d ¯

s ¯

₀

è la soluzione che si ottiene applicando A a d ¯

₀

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

(2)

Programmazione ricorsiva

sottoprogramma che richiama se stesso direttamente (ricorsione diretta) oppure attraverso altri sottoprogrammi (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)!

funzione

recursive function fact(n) result(f) integer, intent(in) :: n

integer :: f if (n==0) then

f=1 else

f=n*fact(n-1) end if

end function fact

(3)

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)

funzione

recursive function fib(n) result(f) integer, intent(in) :: n

integer :: f if (n<=1)then

f=1 else

f=fib(n-1)+fib(n-2) end if

end function fib

(4)

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

s

_j:m

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

Stringa palindroma - II

funzione

recursive function isPalindrome(st) result(f) character(len=*), intent(in) :: st

logical :: f integer :: i

if (len_trim(st)<=1)then f=.TRUE.

else

f=st(1:1)==st(len_trim(st):len_trim(st)) &

.AND. isPalindrome(st(2:len_trim(st)-1)) end if

end function isPalindrome

(5)

Stringa palindroma - III

traccia di esecuzione per la stringa "radar"

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

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

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

<-- true

Stringa palindroma - IV

traccia di esecuzione per la stringa "alma"

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

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

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

<-- false

(6)

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

integer :: f f=n*fact(n-1) end function fact

recursive function isPalindrome(st) result(f) character(len=*), intent(in) :: st

logical :: f integer :: i

f=st(1:1)==st(len_trim(st):len_trim(st)) &

.AND. isPalindrome(st(2:len_trim(st)-1)) end function isPalindrome

(7)

Errori nella ricorsione - II

test errato nella CDT

integer :: f if (n>0) then

f=1 else

f=n*fact(n-1) end if

end function fact

logical :: f; integer :: i if (len_trim(st)<0)then

f=.TRUE.

else

.AND. isPalindrome(st(2:len_trim(st)-1)) end if

end function isPalindrome

Errori nella ricorsione - III

non si converge nella RDR

integer :: f if (n==0) then

f=1 else

f=n*fact(n+1) end if

end function fact

logical :: f; integer :: i if (len_trim(st)<=1)then

f=.TRUE.

else

.AND. isPalindrome(st(1:len_trim(st))) end if

end function isPalindrome

(8)

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

function fact(n) result(f) integer,intent(in) :: n integer :: f

integer :: i f=1

do i=2,n f=f*i end do

end function fact

fibonacci

function fib(n) result(f) integer,intent(in) :: n integer :: f

integer :: k,f1,f2 f=1;f1=f;f2=f do k=2,n

f = f1 + f2; f2 = f1; f1 = f end do

end function fib

(9)

Zero di una funzione - I

definizione

zero( F _, _x

₀

_, _x

₁

_{) = x}

₀

se |x

₀

− x

₁

| ≤ ε zero( F , x

₀

, x

₁

) = zero( F ,

^x⁰^+x₂ ¹

, x

₁

)

se sign( F ₍

^x⁰^+x¹

2

)) = sign( F _(x

₀

₎₎

zero( F _, _x

₀

_, _x

₁

_{) = zero(} F _, _x

₀

_,

^x⁰^+x¹

2

) altrimenti

Zero di una funzione - II

funzione

recursive function zero(func,x0,x1) result(ris) interface

function func(x) result(y)

real,intent(in) :: x; real :: y end function func

end interface

real,intent(in) :: x0,x1

real :: ris; real :: x;logical :: segnomeno segnomeno = func(x0) < 0

if ((func(x1) < 0) .eqv. segnomeno) then print *,"Errore"; ris=0.0

else if (abs(x0 - x1) < EPS) then ; ris=x0 else

x = (x0 + x1) / 2.0

if ((func(x) < 0) .eqv. segnomeno) then ris=zero(func,x,x1)

else

ris=zero(func,x0,x) end if

end if

end function zero Ricorsione, Paolo Bison, FI08, 2008-09-29 – p.18

(10)

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

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

programma hanoi.f90

(11)

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)

•

Paolo Bison

Ricorsione

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

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

) = ¯s

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

))

dove

d ¯ , d ¯

e d ¯

sono tre insiemi di dati con d ¯ 6= ¯ d

e

d ¯

“più semplice” di d ¯

s ¯

è la soluzione che si ottiene applicando A a d ¯

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

Programmazione ricorsiva

sottoprogramma che richiama se stesso direttamente (ricorsione diretta) oppure attraverso altri sottoprogrammi (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)!

funzione

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

funzione

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)

è la lunghezza della stringa s

s

è l’i-esimo carattere

s

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

Stringa palindroma - II

funzione

recursive function isPalindrome(st) result(f) character(len=*), intent(in) :: st

logical :: f integer :: i

if (len_trim(st)<=1)then f=.TRUE.

else

f=st(1:1)==st(len_trim(st):len_trim(st)) &

.AND. isPalindrome(st(2:len_trim(st)-1)) end if

end function isPalindrome

Stringa palindroma - III

traccia di esecuzione per la stringa "radar"

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

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

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

<-- true

<-- true

(1) A _{( ¯} _d

_{) = ¯s}

(2) A _{( ¯} _d _{) =} F ₍ A _{( ¯} _d

₎₎

zero( F _, _x

_, _x

_{) = x}

se sign( F ₍

)) = sign( F _(x

₎₎

zero( F _, _x

_, _x

_{) = zero(} F _, _x

_,

| | |

| | |

| | |

Hanoi (n − 1,t, l) dove k, l,t ∈ {1, 2, 3} ^e k 6= l, l 6= t ^e k 6= t