Le funzioni ricorsive su Matlab

In questa lezione ti spiego come creare una funzione ricorsiva su Matlab

Cos'è la ricorsione? Una funzione è detta funzione ricorsiva se richiama se stessa una o più volte. La ricorsione è alla base della programmazione funzionale.

Ti faccio un esempio pratico.

Per calcolare il fattoriale (n!) di un numero puoi definire e utilizzare questa funzione ricorsiva.

function y = fact(x)
if (x<0)
disp("numero negativo")
return;
end
if (x<2)
y=1;
return;
else
y=x*fact(x-1);
end
end

La funzione fact() è una funzione ricorsiva perché richiama se stessa nell'istruzione y=x*fact(x-1).

Come funziona

La funzione fact() riceve un numero x in entrata tramite la chiamata

• Se x<0
  Se il numero x è negativo la funzione non fa nulla perché il fattoriale di un numero negativo non esiste. In questo caso la funzione stampa "numero negativo" e restituisce il controllo al programma chiamante tramite l'istruzione return.
  
• Se 0≤x<2
  Se il numero x è un numero positivo minore di 2 la funzione restituisce 1. In questo caso termina la ricorsione perché la funzione non richiama se stessa. L'istruzione return restituisce il valore 1 alla precedente chiamata ricorsiva della funzione. Quindi, il processo torna indietro chiudendo man mano le precedenti chiamate ricorsive.
  
• Se x≥2
  Se il numero x è maggiore o uguale a 2 la funzione moltiplica il numero x per il risultato della funzione fact(x-1). Dove x-1 è il numero intero corrente (x) meno uno. In questo caso la funzione richiama se stessa fact(x-1) compiendo una ricorsione.
  

Ad esempio, richiama la funzione fact() con il numero x=6.

n=6;
y=fact(n);
disp(y)

function y = fact(x)
if (x<0)
disp("numero negativo")
return;
end
if (x<2)
y=1;
return;
else
y=x*fact(x-1);
end
end

Nota. Ricorda che una funzione in Matlab deve essere sempre definita alla fine dello script.

La funzione riceve in ingresso il numero x=6 e inizia calcolare il fattoriale 6! in modo ricorsivo.

La funzione richiama se stessa 5 volte (ricorsione) passando ogni volta un numero inferiore al precedente.

fact(6)=6*fact(5)
fact(5)=5*fact(4)
fact(4)=4*fact(3)
fact(3)=3*fact(2)
fact(2)=2*fact(1)

Nell'ultima chiamata fact(1)=1 la funzione restituisce 1 chiudendo le ricorsioni precedenti.

Se fact(1)=1 allora fact(2)=2 perché fact(2)=2*fact(1)=2*1=2

fact(6)=6*fact(5)
fact(5)=5*fact(4)
fact(4)=4*fact(3)
fact(3)=3*fact(2)
fact(2)=2*fact(1)=2*1=2

Se fact(2)=2 allora fact(3)=6 perché fact(3)=3*fact(2)=3*2=6

fact(6)=6*fact(5)
fact(5)=5*fact(4)
fact(4)=4*fact(3)
fact(3)=3*fact(2)=3*2=6

Se fact(3)=6 allora fact(4)=24 perché fact(4)=4*fact(3)=4*6=24

fact(6)=6*fact(5)
fact(5)=5*fact(4)
fact(4)=4*fact(3)=4*6=24

Se fact(4)=24 allora fact(5)=120 perché fact(5)=5*fact(4)=5*24=120

fact(6)=6*fact(5)
fact(5)=5*fact(4)=5*24=120

Se fact(5)=120 allora fact(6)=720 perché fact(6)=6*fact(5)=6*120=720

fact(6)=6*fact(5)=6*120=720

Pertanto il fattoriale di 6! è 120

$$ 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720 $$

Alle fine del calcolo lo script restituisce 720 ossia il fattoriale di 6!

720