Problemi e grafici ricorsivi
Dalla definizione ricorsiva alle strutture complesse: numeri, grafici e immagini tra successioni, alberi e autosimiglianza.
Nell’ampia e luminosa galleria della storia, che espone il lascito culturale di Leonardo Fibonacci, fa bella mostra di sé il celebre problema dei conigli:
«Quante coppie di conigli verranno prodotte in un anno, a partire da un’unica coppia, se ogni mese ciascuna coppia dà alla luce una nuova coppia che diventa produttiva a partire dal secondo mese?».
Il numero di coppie è, di mese in mese e oltre, nella successione che porta il suo nome: la successione di Fibonacci:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
Una successione generabile in modo ricorsivo a partire da due soli valori iniziali:
$$
begin{cases}
f(n)=f(n-1)+f(n-2), & n>2[4pt] f(1)=1,quad f(2)=1
end{cases}
$$
La ricorsività entra così in scena con il suo tratto distintivo: una legge che si applica a se stessa, generando una struttura che nasce e cresce a partire dai propri risultati precedenti. Ogni termine, infatti, è la somma dei due precedenti.
La successione di Lucas
La stessa legge di ricorsione può dar luogo a successioni numeriche diverse semplicemente variando i valori iniziali. È il caso della successione di Lucas, da Édouard Lucas (1842–1891), autore della classica opera Récréations Mathématiques, definita da:
$$
begin{cases}
l(n)=l(n-1)+l(n-2), & n>2[4pt] l(1)=1,quad l(2)=3
end{cases}
$$
Da cui si ottiene:
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …
La ricorsione è la stessa di Fibonacci, ma la diversa scelta delle condizioni iniziali modifica l’intera successione.
È un primo insegnamento: la ricorsività è
