L'approccio top-down alla risoluzione dei problemi consiste in una analisi che conduce alla scomposizione del problema in sottoproblemi più semplici. Può essere descritto nel modo seguente
Risolvere il problema P:
se è nota una risoluzione di P
allora
applicarla
altrimenti
scomporre P in sottoproblemi P(1), P(2),...,P(n)
risolvere il problema P(1)
......
risolvere il problema P(n)
Può accadere che almeno uno dei sottoproblemi sia lo stesso problema in esame. Si ha allora a che fare con una analisi detta "ricorsiva" che, quando è corretta, può essere estremamente proficua.
Ad esempio la potenza intera di un numero può essere definita in modo iterativo:an = a*a*a*....*a (n volte)oppure in modo ricorsivo:
1 se n=0 e a<>0
an =
an-1 * a se n > 0
Il classico algoritmo di Euclide per calcolare il M.C.D. tra due numeri naturali
può essere descritto ricorsivamente nel modo seguente:
Calcolare il M.C.D. tra a e b:
se a=b
allora
il M.C.D. è a
altrimenti
se a>b
allora
il M.C.D. è il M.C.D. tra a-b e b
altrimenti il M.C.D. è il M.C.D. tra a e b-a
E` ciò
che si potrebbe anche scrivere
a se a=b
M.C.D.(a,b)= M.C.D.(a-b,b) se a>b
M.C.D.(a,b-a) altrimenti
con formalismo matematico compatto ed elegante. Possiamo anche in
questo caso provare a descrivere i passi per
calcolare il M.C.D. tra 12 e 16:
calcolare il M.C.D. tra 12 e 4:
calcolare il M.C.D. tra 8 e 4:
calcolare il M.C.D. tra 4 e 4:
il M.C.D. è 4
Anche la trasformazione di base:
trasformare, da base dieci ad altra base, un numero:
se numero <> 0
allora
trasformare il quoziente tra numero e base nell'altra base
registrare il resto tra numero e base tradotto nelle cifre dell'altra base
Applichiamo il procedimento ad esempio per
trasformare 9 in base due:
trasformare 4 in base due:
trasformare 2 in base due:
trasformare 1 in base due:
trasformare 0 in base due:
registrare 1
registrare 0
registrare 0
registrare 1.
La combinatoria è per sua natura un dominio del pensiero ricorsivo.
Infatti per
permutare una lista di n oggetti:
se ci sono oggetti
allora
estrarre un oggetto e porlo in testa
permutare il resto e porlo in coda
altrimenti
la permutazione è una lista vuota.
oppure
per disporre n oggetti k alla volta:
se ci sono oggetti e k > 0
allora
estrarre un oggetto
disporre gli n-1 oggetti restanti k-1 alla volta
altrimenti
la disposizione è una lista vuota.
Il numero
delle disposizioni di n oggetti presi k alla volta saranno dunque
1 se k=0
Dn,k =
n * Dn-1,k-1 se k <= n
Invece per
combinare n oggetti k per volta:
se n = k oppure k = 0
allora
la combinazione è la lista costituita dagli stessi oggetti oppure è vuota
altrimenti
combinare gli oggetti, tolto il primo, k-1 per volta
inserire il primo oggetto in testa alle combinazioni ottenute
combinare gli oggetti, tolto il primo, k per volta
Ad esempio si vogliano combinare abcd 2 alla volta. Otterremo:
ab, ac, ad, bc, bd, cd.Il numero delle combinazioni di n oggetti presi k alla volta, come i numeri del triangolo di Pascal-Tartaglia, ovvero i coefficienti binomiali, saranno dunque definiti ricorsivamente da:
1 se k=0 oppure n=k
Cn,k=
Cn-1,k-1 + Cn-1,k se k < n
La successione di Fibonacci,
definita sinteticamente come
1 se i = 1 , 2
f(i) =
f(i-2) + f(i-1) se i > 2
è storicamente associata ad un problema, quello della crescita di una famiglia
di conigli che si riproducono secondo certe regole, che si risolve facilmente
proprio con stile ricorsivo.
In generale i modelli matematici per rappresentare la crescita di popolazioni si costruiscono molto più facilmente ricorrendo ad uno schema ricorsivo, come nel caso più semplice in cui, detto n il numero di individui in funzione del tempo:
n0 se t=t0
n(t + dt) =
n(t) + a*n(t) se t>t0
essendo a la differenza tra tasso di natalità e tasso di mortalità.
Esempi
Esercizi: