Matematica del discreto

Le definizioni ricorsive

Oltre alle dimostrazioni per induzione, si possono dare anche definizioni per ricorrenza o definizioni ricorsive: come il principio di induzione sono costituite da due affermazioni:
una che stabilisce in modo esplicito il primo elemento,
l'altra che definisce l'elemento generico mediante i precedenti.
Di seguito alcuni esempi:

ESEMPIO 1

Operazione di elevamento a potenza di un numero naturale a > 0: 1) a0 = 1

1) a0 = 1
2) an = an-1 a

ESEMPIO 2

Un'altro esempio di definizione ricorsiva si pu fare con la successione di Fibonacci:

1) a0=0, a1=1
2) an = an-1 + an-2

ESEMPIO 3

Anche ad un numero fattoriale si pu assegnare una definizione ricorsiva. Proviamo a pensare a quanti sono tutti i possibili anagrammi (anche privi di senso) di una data parola. La risposta dipende dal numero n di lettere, che supponiamo differenti.
con 1 lettera abbiamo 1 anagramma soltanto: a
con due lettere 2 anagrammi (2·1): ad, da
con 3 lettere, 6 anagrammi (3·2·1): ape, aep, pae, pea, eap, epa.
con 4 lettere 24 anagrammi (4·3·2·1):
rosa, roas, rsoa, rsao, raos, raso,
orsa, oras, osra, osar, oars, oasr,
sroa, srao, sora, soar, saro, saor,
aros, arso, aors, aosr, asro, asor.
Gli anagrammi sono le permutazioni di n oggetti. Il numero di permutazioni di n oggetti 123 ...n.
Questo numero si chiama fattoriale di n, si indica con il simbolo n!. La definizione ricorsiva di n! sar:

1) 1! = 1
2) n! = (n - 1)!n.

Risulta utile definire anche 0!; si pone per convenzione 0!=1, e allora la definizione ricorsiva si modifica nel seguente modo:

1) 0! = 1
2) n! = (n - 1)!n.

ESEMPIO 4

Anche al triangolo di Tartaglia pu essere attribuita una definizione ricorsiva, in quanto ogni elemento la somma dei due numeri della riga precedente che gli "stanno sopra", a destra e a sinistra.

















Tutto quanto riportato in questa pagina a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione fondamentale per la continua crescita del sito.