Ricorsione e Iterazione

Fondamenti dell’Informatica

Ricorsione e Iterazione

Simona Ronchi Della Rocca

(dal testo: Kfoury, Moll and Arbib, cap.5.2)

Definiamo innanzitutto una relazione d’ordine tra le funzioni. Siano φ e ψ funzioni unarie da naturali a naturali:

φ ≤ ψ (φ `e minore di ψ, o φ approssima ψ) se e solo se ∀x ∈ dom(φ).φ(x) = ψ(x). Cio`e, dove la minore `e definita, `e definita anche la maggiore, e assumono entrambe lo stesso valore. Diciamo inoltre che φ < ψ (φ `e strettamente minore di ψ) se e solo se φ ≤ ψ ed esiste ameno un valore x dove ψ `e definita e φ no.

Ad esempio, la funzione:

h(x) =

 x se x `e pari

⊥ altrimenti

`e tale che h ≤ Id e anche h < Id (Id `e la funzione identit`a).

Consideriamo una semplice funzione ricorsiva:

f att(x) = se x = 0 allora 1 altrimenti x ∗ f att(x − 1) fatt pu`o essere approssimata dalla seguente catena di funzioni parziali:

f att⁽⁰⁾(x) =

 1 se x = 0

⊥ altrimenti

f att⁽¹⁾(x) =

 1 se x = 0, 1

⊥ altrimenti f att⁽ⁿ⁾(x) =

 1 ∗ 2 ∗ ... ∗ x se x ≤ n

⊥ altrimenti

tali che:

f att⁽⁰⁾ < f att⁽¹⁾< ... < f att⁽ⁿ⁾< f att⁽ⁿ⁺¹⁾< ...

Se dobbiamo calcolare il fattoriale del numero m, ci baster`a usare una approssi- mazione f att<sup>(n)</sup>, con n ≥ m. In altre parole, la definizione ricorsiva di una funzione pu`o essere sviluppata all’infinito, ma ogni volta che vogliamo calco- larla su di uno specifico valore, il numero degli sviluppi (chiamate ricorsive) `e sempre finito e dipende dal valore in input. In altre parole nella computazione reale non ci serve mai tutta la potenza della ricursione.

Fatte queste considerazioni preliminari, vogliamo ora mostrare l’equivalenza tra ricursione e iterazione. Cio`e vogliamo dimostrare il seguente teorema:

Teorema. Dato un programma ricorsivo, esiste un programma iterativo che calcola la stessa funzione.

Estendiamo il linguaggio WHILE con una nozione di procedura ricorsiva, come fatto nel testo a pag. 110 (versione inglese), con la semantica operazionale come data informalmente nel testo. Sia FATT il programma cos`ı ottenuto.

Possiamo scrivere, per ogni n, il programma iterativo che calcola la funzione f att⁽ⁿ⁾. Sia e l’indice del seguente programma, che calcola la funzione ovunque indefinita:

Pe= begin X1 = 1; while X1 6= 0 do begin end end Sia F AT T⁰=

begin if X1 = 0 then X1 := 1 else begin X2 := X1; X1 := pred(X1);

Pe;

X1 := X2 ∗ X1 end

end

Ovviamente F AT T⁰ calcola la funzione f att⁰. Sia ora F AT T₊⁰ il programma F AT T⁰ con X3 al posto di X2, cio`e modificato nel seguente modo:

begin if X1 = 0 then X1 := 1 else begin X3 := X1; X1 := pred(X1);

Pe;

X1 := X3 ∗ X1 end

end Sia F AT T¹=

begin if X1 = 0 then X1 := 1 else begin X2 := X1; X1 := pred(X1);

F AT T₊⁰; X1 := X2 ∗ X1

end end

La ridenomina della variabile X2 in X3 `e necessaria per poter effettuare il passaggio dei parametri, senza cancellare il dato iniziale. Ovviamente F AT T¹ calcola la funzione f att¹.

Sia f la funzione di riscrittura di programmi tale che, applicata ad un pro- gramma di indice i, lo riscrive nel modo seguente, ottenendo cos`ı il programma di indice f (i):

begin if X1 = 0 then X1 := 1 else begin X2:= X1; X1 := pred(X1);

Pi dove ogni variabile Xj, con j ≥ 2 `e rimpiazzata da Xj+1; X1 := X2 ∗ X1

end end

Quindi F AT T⁰= P_{f (e)}, e possiamo allora scrivere F AT T¹ nel modo seguente:

begin if X1 = 0 then X1 := 1 else begin X2 := X1; X1 := pred(X1);

P_{f (e)};

X1 := X2 ∗ X1 end

end

cio`e F AT T¹= P_f2(e), usando la notazione:

f⁰(e) = e, fⁿ⁺¹(e) = f (fⁿ(e)).

In generale, la funzione f att⁽ⁿ⁾sar`a quindi calcolata dal programma F AT Tⁿ = Pfⁿ⁺¹(e), definito nel modo seguente:

begin if X1 = 0 then X1 := 1 else begin X2 := X1; X1 := pred(X1);

Pfⁿ(e);

X1 := X2 ∗ X1 end

end In altre parole,

φ_fn+1(e)(a) = f attⁿ(a)

Teorema. Per ogni n, esiste m tale che f att^(m)(n) = f att(n).

Dimostrazione. Ovvia, basta prendere m = n.

Possiamo quindi scrivere un programma iterativo, che calcola il fattoriale, calcolando prima quale `e l’approssimazione necessaria, e poi applicando questa all’input? Invece di riferirci solo alla funzione fattoriale, vediamo di porci il problema nel caso pi`u generale.

Sia k una funzione definita in modo ricorsivo. k `e approssimata da una catena infinita di funzioni parziali:

k⁽⁰⁾< k⁽¹⁾< ... < k⁽ⁿ⁾< k⁽ⁿ⁺¹⁾< ...

Vale in generale un teorema simile al precedente:

Teorema. Per ogni n, esiste m tale che k^(m)(n) = k(n).

Possiamo scrivere, analogamente a quanto fatto per il fattoriale, un pro- gramma iterativo che calcola ciascuna delle approssimazioni k⁽ⁱ⁾(i ≥ 0). Siano Kⁱ questi programmi. Ricordiamo che ciscuno di questi programmi richiama al suo interno il programma Pe, che cicla indefinitamente. Analogamente a quanto fatto per la funzione fattoriale, possiamo definire una sequenza di programmi, K⁰, K¹, ... tali che Kⁱ calcola la funzione k⁽ⁱ⁾. Esiste quindi una funzione di

riscrittura di programmi, sia fk, tale che Kⁿ= P_fn+1

k (e). Possiamo scrivere un programma iterativo, che calcola k, calcolando prima quale `e l’approssimazione necessaria, e poi applicando il programma corrispondente all’input?

Cio`e, `e possibile implementare il seguente algoritmo, per ogni funzione k e programmi Kⁱ?

Algoritmo A:

1. sia a il dato in input;

2. calcola quale `e il minimo m tale che k^(m)(a) = k(a);

3. esegui il programma K^msull’input a.

NOTA. Questo programma NON `e ricorsivo, perch`e i programmi che cal- colano le approssimazioni k⁽ⁿ⁾ sono programmi iterativi.

Il problema, per implementare l’algoritmo A, `e che non possiamo procedere per tentativi, ad esempio provando ad eseguirlo nel modo seguente:

1. sia a il dato in input;

2. poni n = 0;

3. esegui Kⁿ sull’input a e va a 4;

4. se l’esecuzione di Kⁿ sull’input a `e terminata normalmente, esci dando in output il contenuto di X1;

5. se l’esecuzione di Kⁿ non termina, incrementa n di 1 e torna a 3.

infatti tale algoritmo non `e implementabile, data l’indecidibilit`a del problema dell’alt.

Possiamo per`o rendere effettivo l’algoritmo, trasformandolo nel modo seguente.

Sia F LAG una variabile speciale e sia P_u il seguente programma:

P_u= begin F LAG := 1 end

e trasformiamo ogni programma Kⁿ sostituendo, al posto di P_e, il programma Pu. Quindi Kⁿ = P_fn+1

k (u).

Ricordiamoci che ogni programma Kⁿ ha come indice f_kⁿ⁺¹(e), e quindi il programma trasformato avr`a come indice f_kⁿ⁺¹(u).

La differenza tra P_fn

k(e) e il programma trasformato P_fn

k(u) `e che, mentre il primo pu`o ciclare, per particolari valori di input, il programma trasformato termina sempre, e in particolare pone F LAG = 1 in corrispondenza ai valori di input per cui P_fⁿ

k(e)cicla.

Possiamo quindi scrivere il seguente algoritmo B:

1. sia a il dato in input;

2. n:=1;

3. FLAG:=0; esegui P_fⁿ

k(u) (cio`e il trasformato di Kⁿ) sull’input a. Se e quando la computazione si ferma, va a 4;

4. Se FLAG =1, incrementa n di 1 e va a 3;

5. Se FLAG=0, restituisci in output il valore di X1.

Infatti FLAG =1 indica che `e stato eseguito P_u, il che corrisponderebbe all’esecuzione di P_enel programma originale Kⁿ.

Possiamo scrivere un programma WHILE che realizza l’algoritmo B. Sia h la funzione di riscrittura di programmi tale che P_h(x) `e il programma seguente:

begin F LAG := 0;

{Px dove ogni test C `e trasformato in C AND FLAG=0}

if F LAG = 0 then X1 := succ(X1) else X1 := 0 end

Il programma P_h(fn+1

k (u)) calcola la seguente funzione:

φ_h(fn+1

k (u))(a) =

 φ_fn+1

k (e)(a) + 1 = kⁿ(a) + 1 se Pfⁿ

k(e)su a non cicla

0 altrimenti

Quindi l’algoritmo B `e implementato dal seguente programma:

begin N := 0; while Φ(h(f_k^N(u)), X1) = 0 do N := succ(N );

X1 := pred(Φ(h(f_k^N(u)), X1)) end

che calcola quindi, in modo iterativo, la funzione k.

Quindi abbiamo dimostrato il teorema voluto:

Theorema Per ogni programma ricorsivo, c’`e un programma iterativo che calcola la stessa funzione.