Funzioni ricorsivecassano.faculty.polimi.it/Lez11_Ricorsione_FunzioniOr... · 2018. 11. 30. ·...

Informatica B, AA 18/19, Luca Cassano

Funzioni ricorsive

Informatica B AA 18/19

Luca Cassano

[email protected]

3 Dicembre 2018

mailto:[email protected]


Richiami sulle funzioni


Un esempio

function f = fattoriale(n)

f = 1;

for ii = 2 : n

f = f * ii;

end


Un esempio


f = 1;

for ii = 2 : n

f = f * ii;

end

Parametro formale in ingresso

Parametro formale in uscita

Definizione di 𝒏!Il fattoriale di un intero 𝑛 > 0 è definito come segue:

𝑛! = 𝑛 ∗ 𝑛 − 1 ∗ 𝑛 − 2 ∗ ⋯∗ 2 ∗ 1


Un esempio di chiamata

fattoriale(2)

ans =

2


f = 1;

for ii = 2 : n

f = f * ii;

end



fattoriale(2)

ans =

2


f = 1;

for ii = 2 : n

f = f * ii;

end

Parametro attuale in ingresso

Parametro attuale in uscita



k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end

Workspace principale Workspace locale

• Da qui si invoca la funzione

• Contiene le variabili k, f2

• Non ha visibilità di f,ii,n

• Creato al momento

dell’invocazione di fattoriale

• Contiene le variabili n, f,ii

• Non ha visibilità su k ed f2

• Non ha legami con il workspace

principale se non per i parametri

attuali che vengono copiati

• Distrutto terminata l’esecuzione



k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end









k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end







• Contiene le variabili n, f, ii



k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end











k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end











attuali che vengono copiati (sia in

ingresso che in uscita)



k = 2;

f2 = fattoriale(k);


f = 1;

for ii = 2 : n

f = f * ii;

end











attuali che vengono copiati (sia in

ingresso che in uscita)

• Distrutto terminata l’esecuzione


Esempi

f2 = fattoriale(2)

f2 =

2

f3 = fattoriale(3)

f3 =

6

f4 = fattoriale(4)

f4 =

24

f5 = fattoriale(5)

f5 =

120

f6 = fattoriale(6)

f6 =

720



x = f(2)

x =

2

function xx = f(yy)

……

z = g(yy);

xx = 2 * z;

end

function zz = g(kk)

zz = kk / 3;

end


Un esempio

Si dimostra immediatamente dalla definizione di fattoriale

𝑛! = 𝑛 ∗ 𝑛 − 1 ∗ 𝑛 − 2 ∗ ⋯∗ 2 ∗ 1

Vale la seguente relazione

𝑛! = 𝑛 ∗ 𝑛 − 1 !

𝑛 − 1 !


Un esempio

Si dimostra immediatamente dalla definizione di fattoriale

𝑛! = 𝑛 ∗ 𝑛 − 1 ∗ 𝑛 − 2 ∗ ⋯∗ 2 ∗ 1

Vale la seguente relazione

𝑛! = 𝑛 ∗ 𝑛 − 1 !

È possibile usare questa proprietà per definire

un’implementazione di fattoriale totalmente diversa?

𝑛 − 1 !


Ricorsione

Funzioni che chiamano se stesse


Ricorsione

Che cos’è la ricorsione?


Ricorsione


• Un sottoprogramma P richiama se stesso

(ricorsione diretta)P


Ricorsione



(ricorsione diretta)

• Un sottoprogramma P richiama un

sottoprogramma Q che comporta un’altra

chiamata a P (ricorsione indiretta)

P

P

Q


Ricorsione







È una tecnica di programmazione molto potente

P

P

Q


Ricorsione








Permette di risolvere in maniera elegante problemi

complessi

P

P

Q


Ricorsione








Permette di risolvere in maniera elegante problemi

complessi

Le funzioni che richiamano se stesse (direttamente o

indirettamente) sono dette funzioni ricorsive

P

P

Q


Esempio: il fattoriale Ricorsivo

function [f] = factRic(n)

if (n == 0)

f = 1;

else

f = n * factRic(n - 1);

end


29



if (n == 0)

f = 1;

else


end

Questa ci ricorda

0! = 1


30



if (n == 0)

f = 1;

else


end

Questa ci ricorda

𝑛! = 𝑛 ∗ 𝑛 − 1 !


31



if (n == 0)

f = 1;

else


end

Una funzione che chiama se stessa


Una Funzione che Chiama se Stessa?

In ogni istante possono essere in corso diverse

attivazioni (istanze) dello stesso sottoprogramma

32





• Ovviamente sono tutte sospese tranne una, l'ultima

invocata, all'interno della quale si sta svolgendo il

flusso di esecuzione.

33








Ogni attivazione esegue lo stesso codice ma opera su

workspace distinti (in Matlab, ogni funzione attivata ha

un workspace distinto)

34








Ogni attivazione esegue lo stesso codice ma opera su

workspace distinti (in Matlab, ogni funzione attivata ha

un workspace distinto)

• Si hanno quindi copie distinte dei parametri attuali e

delle variabili locali nelle varie invocazioni

35


Una funzione che chiama se stessa?

… se ogni volta la funzione richiama se stessa… perché la catena di invocazioni non continua all'infinito?

36


Una funzione che chiama se stessa?

… se ogni volta la funzione richiama se stessa… perché la catena di invocazioni non continua all'infinito?

La funzione ricorsiva deve prevedere una situazione in cui non richiama se stessa, i.e., il caso base

37


38

Programmazione Ricorsiva

Per risolvere un problema attraverso la programmazione

ricorsiva sono necessari alcuni elementi


39




• Caso base: caso elementare del problema che può

essere risolto immediatamente. Il caso base non deve

eseguire alcuna chiamata ricorsiva.


40







• Passo ricorsivo: chiamata ricorsiva per risolvere uno o

più problemi più semplici


41









• Costruzione della soluzione: costruzione della

soluzione sulla base del risultato delle chiamate

ricorsive


42









• Costruzione della soluzione: costruzione della

soluzione sulla base del risultato delle chiamate

ricorsive

Affinché l’esecuzione della funzione

termini è fondamentale che la soluzione

ricorsiva converga verso il caso base


43

Esempio: il fattoriale

Definizione:

f(n) = n! = n*(n-1)*(n-2)*…*3*2*1

Definire caso base, e passo ricorsivo


44


Definizione:

f(n) = n! = n*(n-1)*(n-2)*…*3*2*1

Passo ricorsivo:

f(n) = n*f(n-1)

Caso base:

f(0)=1


45


Definizione:

f(n) = n! = n*(n-1)*(n-2)*…*3*2*1

Passo ricorsivo:

f(n) = n*f(n-1)

Caso base:

f(0)=1function [f]=factRic(n)

if (n==0)

f=1;

else

f=n*factRic(n-1);

end


46

Funzionamento ricorsione

function [f]=factRic(n)

if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRicfactRic(3)


47



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

factRic(3)


48



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

n:1 f: ...factRic

factRic(3)


49



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

n:1 f: ...factRic

n:0 f: ...factRic

factRic(3)


50



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

n:1 f: ...factRic

n:0 f: 1factRic

factRic(3)


51



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

n:1 f: ...factRic

n:0 f: 1factRic

factRic(3)


52



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: ...factRic

n:1 f: 1factRic

factRic(3)


53



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: ...factRic

n:2 f: 2factRic

factRic(3)


54



if (n==0)

f=1;

else

f=n*factRic(n-1);

end

n:3 f: 6factRicfactRic(3)

ans =

6


Ricorsione in Coda

Ricorsione in cui la funzione:

• prevede una sola chiamata ricorsiva

• esegue la chiamata ricorsiva come ultima istruzione


if (n==0)

f=1;

else

f=n*factRic(n-1);

end

55


56

Problemi nell’Uso della Ricorsione

Terminazione della catena ricorsiva

• È presente il caso base?

• Viene raggiunto sempre dalla catena di chiamate

ricorsive?


Errori nell’Uso della Ricorsione

Catena infinita di chiamate incondizionate

• Deve esistere una condizione tale per cui non viene

eseguita la chiamata ricorsiva (caso base)


f=n*factRic(n-1);

57




• Deve esistere una condizione tale per cui non viene

eseguita la chiamata ricorsiva (caso base)

Es la chiamata a factRic(7) chiama factRic(7),

che chiama factRic(6),



che chiama factRic(3),….

che chiama factRic(-1000),….


f=n*factRic(n-1);

58




• è necessario che questa condizione venga

raggiunta: anche programmi formalmente corretti

potrebbero non funzionare per alcuni valori degli

ingressi


if (n==0)

f=1;

else

f=n*factRic(n-1);

end

59




• è necessario che questa condizione venga

raggiunta: anche programmi formalmente corretti

potrebbero non funzionare per alcuni valori degli

ingressi

• Ad es, factRic(-1) da luogo ad una sequenza di

chiamate infinite


if (n==0)

f=1;

else

f=n*factRic(n-1);

end

60



Catena infinita di chiamate identiche:

• La chiamata ricorsiva non può avere i parametri

formali uguali a quelli attuali


if (n==0)

f=1;

else

f=n*factRic(n);

end

61



Catena infinita di chiamate identiche:

• La chiamata ricorsiva non può avere i parametri

formali uguali a quelli attuali

Es la chiamata a factRic(7) chiama factRic(7),




che chiama factRic(7),….


if (n==0)

f=1;

else

f=n*factRic(n);

end

62


Di Default…

Matlab si blocca le chiamate ricorsive dopo un po’

>> factRic(600)

Out of memory. The likely cause is an infinite

recursion within the program.

Error in fatRic at line XXX

dove XXX indica la riga in cui compare la chiamata ricorsiva

63


Condizioni Necessarie

.. Per evitare ricorsione infinita:

Occorre che le chiamate ricorsive siano soggette a una condizione che prima o poi assicura che la catena termini

Occorre anche che l'argomento sia progressivamente modificato dal passo ricorsivo, in modo da tendere prima o poi al caso base• Nella pratica l’argomento si avvicina al valore nel caso

base

64


Esempio

Scrivere una funzione ricorsiva che calcola la somma di tutti

gli interi compresi tra due argomenti passati come parametri

65


Esempio



function somma = sommaNumeriCompresi(a ,b)

end

66


Esempio




if

else

end

end

67


Esempio




if a == b

else

end

end

68


Esempio




if a == b

somma = a;

disp(['caso base somma vale ' , num2str(somma)]);

else

end

end

69


Esempio




if a == b

somma = a;


else

disp(['prima chiamata a = ' ,num2str(a)]);

somma = a + sommaNumeriCompresi(a+1 , b);

disp(['dopo chiamata a = ' ,num2str(a)]);

end

end

70


71

Esempio

b:6 somma: ...sommaNumeriCompresi(3 ,6) a:3


72

Esempio


b:6 somma: ...a:4sommaNumeriCompresi(4 ,6)


73

Esempio


b:6 somma: ...a:4

b:6 somma: ...a:5

sommaNumeriCompresi(4 ,6)



74

Esempio


b:6 somma: ...a:4

b:6 somma: ...a:5

b:6 somma: ...a:6





75

Esempio

b:6 somma: ...a:3

b:6 somma: ...a:4

b:6 somma: ...a:5

b:6 somma: 6a:6






76

Esempio

b:6 somma: ...a:3

b:6 somma: ...a:4

b:6 somma: ...a:5

b:6 somma: 6a:6






77

Esempio

b:6 somma: ...a:3

b:6 somma: ...a:4

b:6 somma: 11a:5





78

Esempio

b:6 somma: ...a:3

b:6 somma: 15a:4




79

Esempio

b:6 somma: 18a:3sommaNumeriCompresi(3 ,6)


Esempio

Qual è il problema nella soluzione proposta?

80


Esempio


Cosa succede se a > b?

81


Esempio


Cosa succede se a > b?

Chiamate ricorsive infinite

82


Esempio




if b< a

somma = 0;

end

if a == b

somma = a;


else




end

83


Esempio




if b< a

somma = 0;

end

if a == b

somma = a;


else




end

84

Errore! Non è un caso

base perchè dopo

questo if viene

comunque eseguita la

chiamata ricorsiva


Esempio




if b< a

somma = 0;

return;

end

if a == b

somma = a;


else




end

85

In questo modo l’esecuzione

termina e abbiamo un caso

base corretto.


Esempio




a = min([a, b]);

b = max([a, b]);

if a == b

somma = a;


else




end

86


Le ninfee

Uno stagno contiene n ninfee

• Ogni ninfea in 1 giorno si riproduce di un fattore f (se

f == 2 ogni ninfea ogni giorno genera un’altra ninfea,

se f == 3 ogni ninfea ogni giorno genera due ninfee…)

Scrivere una funzione ricorsiva per calcolare in quanti

giorni la popolazione iniziale di n ninfee ha raggiunto una

cardinalità di N individui dato un fattore f fissato


Soluzione

function gg = stagno(n, f, N)

end


Soluzione


% caso base: se ho già N ninfee nello stagno

% non devo aspettare alcun giorno

if

else

end

end


Soluzione




if (n >= N)

gg = 0;

else

end

end


Soluzione




if (n >= N)

gg = 0;

else

% non abbiamo ancora N ninfee -> chiamata ricorsiva:

% il numero di giorni necessari per coprire lo stagno è

% uguale a: un giorno +

% il numero di giorni che saranno necessari domani

% (quando le ninfee saranno diventate n*f).

end

end


Soluzione




if (n >= N)

gg = 0;

else

% non abbiamo ancora N ninfee -> chiamata ricorsiva:

% il numero di giorni necessari per coprire lo stagno è

% uguale a: un giorno +

% il numero di giorni che saranno necessari domani

% (quando le ninfee saranno diventate n*f).

gg = 1 + stagno(n * f, f, N);

end

end


Esempio

Scrivere una funzione ricorsiva per calcolare la lunghezza di

una stringa

93


Esempio


una stringa

function s = calcolaLunghezza(str)

end

94


Esempio


una stringa


if

else

end

end

95


Esempio


una stringa


if(isempty(str))

s = 0;

else

end

end

96


Esempio


una stringa


if(isempty(str))

s = 0;

else

s = 1 + calcolaLunghezza(str(2 : end));

end

end

97


98

Esempio

s: ...calcolaLunghezza(‘ciao’) str: ciao


99

Esempio


s: ...str: iaocalcolaLunghezza(‘iao’)


100

Esempio


s: ...str: iao

s: ...str: ao

calcolaLunghezza(‘iao’)

calcolaLunghezza(‘ao’)


101

Esempio


s: ...str: iao

s: ...str: ao

s: ...str: o



calcolaLunghezza(‘o’)


102

Esempio


s: ...str: iao

s: ...str: ao

s: ...str: o




s: ...str:calcolaLunghezza(‘’)


103

Esempio


s: ...str: iao

s: ...str: ao

s: ...str: o




s: 0str:calcolaLunghezza(‘’)


104

Esempio


s: ...str: iao

s: ...str: ao

s: ...str: o




s: 0str:calcolaLunghezza(‘’)


105

Esempio


s: ...str: iao

s: ...str: ao

s: 1str: o





106

Esempio


s: ...str: iao

s: 2str: ao




107

Esempio


s: 3str: iaocalcolaLunghezza(‘iao’)


108

Esempio

s: 4calcolaLunghezza(‘ciao’) str: ciao


Esempio

Scrivere una funzione per stampare una stringa al contrario

109


Esempio:


function stampaAlContrario(frase)

% caso base

if

else

end

end

110


Esempio:



% caso base

if isempty(frase)

else

end

end

111


Esempio:



% caso base

if isempty(frase)

% return

else

end

end

112


Esempio:



% caso base

if isempty(frase)

% return

else

disp(frase(end)); % stampa al contrario

end

end

113


Esempio:



% caso base

if isempty(frase)

% return

else

disp(frase(end)); % stampa al contrario

% chiamata ricorsiva

stampaAlContrario(frase(1:end-1))

end

end

114


115

Esempio

disp(‘o’)stampaAlContrario(‘ciao’) str: ciao


116

Esempio


disp(‘a’)str: ciastampaAlContrario(‘cia’)


117

Esempio


disp(‘a’)str: cia

disp(‘i’)str: ci

stampaAlContrario(‘cia’)

stampaAlContrario(‘ci’)


118

Esempio




disp(‘c’)str: c



stampaAlContrario(‘c’)


119

Esempio

disp(‘’)str:stampaAlContrario(‘’)




disp(‘c’)str: c





Esempio:

Modificare la funzione precedente per stampare la stringa

nello stesso ordine in cui è stata inserita

120


Esempio:

Modificare la funzione precedente per stampare la stringa

nello stesso ordine in cui è stata inserita


% caso base

if isempty(frase)

% return

else

% chiamata ricorsiva

stampaAlContrario(frase(1:end-1))

disp(frase(end)); % stampa dritto

end

In questo caso la

ricorsione non è

in coda

121


122

Esempio

stampaAlContrario(‘ciao’) str: ciao


123

Esempio


str: ciastampaAlContrario(‘cia’)


124

Esempio


str: cia

str: ci




125

Esempio


str: cia

str: ci

str: c





126

Esempio

str:stampaAlContrario(‘’)


str: cia

str: ci

str: c





127

Esempio

str:stampaAlContrario(‘’)


str: cia

str: ci

str: c





128

Esempio


str: cia

str: ci

disp(‘c’)str: c





129

Esempio


str: cia

str: ci


stampaAlContrario(‘ci’) disp(‘i’)


130

Esempio


disp(‘a’)str: ciastampaAlContrario(‘cia’)


131

Esempio



Esempio:

Cosa stampa??

function stampa(frase)

% caso base

if isempty(frase)

% return

else

stampa(frase(2:end))

disp(frase(1));

end

132


Esempio:

Cosa stampa??

function stampa(frase)

% caso base

if isempty(frase)

% return

else

stampa(frase(2:end))

disp(frase(1));

end

133

>> stampa(‘ciao’);

>> o

>> a

>> i

>> c


Cosa Stampa?

function stampa(str)

if(isempty(str))

% return

else

disp(str(end));

stampaAlContrario(str(1 : end -1));

disp(str(end));

end


Cosa Stampa?

function stampaAlContrario(str)

if(isempty(str))

% return

else

disp(str(end));


disp(str(end));

end

>> stampaAlContrario('ciao')

o

a

i

c

c

i

a

o


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(end));

stampaAlContrario(str(2 : end));

disp(str(end));

end


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(end));


disp(str(end));

end


o

o

o

o

o

o

o

o


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(1));


disp(str(1));

end


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(1));


disp(str(1));

end


c

i

a

o

o

a

i

c


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(1));


disp(str(1));

end


Cosa Stampa?


if(isempty(str))

% return

else

disp(str(1));


disp(str(1));

end


c

c

c

c

c

c

c

c


145

I numeri di Fibonacci

• Modello alla base di molte dinamiche evolutive delle

popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

Definizione ricorsiva della successione di Fibonacci


146


• Modello a base di molte dinamiche evolutive delle

popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)



147



popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)

1 passo ricorsivo



148



popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)

1 passo ricorsivo


F(3)


149



popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)

1 passo ricorsivo


F(3)

F(2) F(1)

+


150



popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)

1 passo ricorsivo


F(3)

F(2) F(1)

+

F(1) F(0)

+

1


151



popolazioni

F = {f0, ..., fn}

• f0 = 1

• f1 = 1

• Per n > 1, fn = fn–1 + fn–2

casi base (sono 2!)

1 passo ricorsivo


F(3)

F(2) F(1)

+

F(1) F(0)

+

1 1

1


152

Esempio: Fibonacci

È una sequenza di numeri interi in cui ogni numero si ottiene

sommando i due precedenti nella sequenza. I primi due

numeri della sequenza sono per definizione pari ad 1.

• f1 = 1 (caso base)


• fn = fn-1 + fn-2 (passo ricorsivo)


153

Esempio: Fibonacci

È una sequenza di numeri interi in cui ogni numero si ottiene

sommando i due precedenti nella sequenza. I primi due

numeri della sequenza sono per definizione pari ad 1.



• fn = fn-1 + fn-2 (passo ricorsivo)

function [fib]=FiboRic(n)

if n==1 | n==2

fib=1;

else

fib(n)=FiboRic(n-2)+FiboRic(n-1);

end


154

Problemi nell’uso della ricorsione

Uso della memoria

• La programmazione ricorsiva comporta spesso un uso

inefficiente della memoria per la gestione degli spazi di

lavoro delle chiamate generate

• In alcuni casi (che non abbiamo il tempo di vedere) viene

comunque preferita ad altri approcci per la sua eleganza e

semplicità

• In altri casi, si può ricorrere ad implementazioni iterative


155

Problemi nell’uso della ricorsione

Uso della memoria

• La programmazione ricorsiva comporta spesso un uso

inefficiente della memoria per la gestione degli spazi di

lavoro delle chiamate generate

• In alcuni casi (che non abbiamo il tempo di vedere) viene

comunque preferita ad altri approcci per la sua eleganza e

semplicità

• In altri casi, si può ricorrere ad implementazioni iterative

function [fl]=Fiblist(n)

fl(1)=1;

fl(2)=1;

for k=3:n

fl(k)=fl(k-2)+fl(k-1);

end

Funzione iterativa che calcola i

primi n numeri di fibonacci


Ricorsione Eccessiva

Soluzione elegante ma dispendiosa: numero molto alto di

chiamate ricorsive fib(6)

fib(4) fib(5)

fib(2) fib(3)

fib(1) fib(2)

fib(3)

fib(1) fib(2)

fib(4)

fib(2) fib(3)

fib(1) fib(2)




chiamate ricorsive

fib(1) viene chiamata 3 volte

fib(6)

fib(4) fib(5)

fib(2) fib(3)

fib(1) fib(2)

fib(3)

fib(1) fib(2)

fib(4)

fib(2) fib(3)

fib(1) fib(2)




chiamate ricorsive

fib(2) viene chiamata 5 volte

fib(6)

fib(4) fib(5)

fib(2) fib(3)

fib(1) fib(2)

fib(3)

fib(1) fib(2)

fib(4)

fib(2) fib(3)

fib(1) fib(2)




chiamate ricorsive

Provate a far calcolare fib(10), fib(15), fib(20), fib(25),

fib(30) ....

Qante volte viene calcolato fab(3)?

Meglio usare una soluzione non ricorsiva...

fib(6)

fib(4) fib(5)

fib(2) fib(3)

fib(1) fib(2)

fib(3)

fib(1) fib(2)

fib(4)

fib(2) fib(3)

fib(1) fib(2)


Esempio

Scrivere una funzione ricorsiva palindroma che controlla se

una stringa è palindroma


Esempio

Scrivere una funzione ricorsiva palindroma che controlla se

una stringa è palindroma

function [res]=controllaPalindromo(stringa)

% stringhe di un carattere (o vuote sono palindrome)

if length(stringa)<2

res=true;

else

% controllo se gli estremi sono uguali

if stringa(1)==stringa(end)

% in tal caso richiama controllaPalindromo su stringa(2, end-1)

res=controllaPalindromo(stringa(2:end-1));

else

res=false;

end

end

Funzioni ricorsivecassano.faculty.polimi.it/Lez11_Ricorsione_FunzioniOr... · 2018. 11. 30. ·...

Documents

Transcript of Funzioni ricorsivecassano.faculty.polimi.it/Lez11_Ricorsione_FunzioniOr... · 2018. 11. 30. ·...