Ricorsione

Dopo aver analizzato gli algoritmi risolutivi consideriamo i pro e i contro di ognuno Metodo risolutivo Pro Contro Ricorsivo Codifica elegante ~n chiamate ricorsive~n moltiplicazioni Iterativo Codifica elementare ~n moltiplicazioni Con formula Numero di operazioni costante Difficile da ricordareNumeri irrazionaliValore approssimato Conclusioni

Dopo aver analizzato il problema e individuati i 3 algoritmi discutiamo la loro complessità in tempo. Algoritmo ricorsivo Il tempo di attesa può essere considerato proporzionale al numero di chiamate ricorsive Il tempo di attesa è esponenziale, anche se con esponente n/2 piuttosto che n, quindi per n molto grande L’algoritmo ricorsivo per il calcolo … Leggi tutto

Se il linguaggio di programmazione prevede la ricorsione… una SUB A può chiamare la SUB A, se stessa, per svolgere lo stesso compito ma con un’stanza diversa La SUB A chiama la SUB A … finché non succede qualcosa (l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva) e si ritorna all’indietro … Leggi tutto

Il problema Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.Sul primo di tali perni sono infilati 64 dischi d’oro, di dimensioni decrescenti, che formano una torre.Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro … Leggi tutto

Un algoritmo di ordinamento