Ricorsione
Nella Ricorsione una funzione richiama più volte se stessa in un procedimento che per costruzione termina dopo un numero finito di volte. Fatto caratterizzante degli algoritmi ricorsivi e l'assenza di cicli ed è proprio l'assenza di cicli che contribuisce a una maggiore leggibilità, eleganza e astrattezza dei programmi ricorsivi rispetto a quelli iterativi. Costruisce una soluzione ricorsiva per un dato problema equivale a dare una definizione per induzione della sua soluzione .
Principio di induzione
E un principio utilizzato per verificare la validità di una produzione che afferma che qualcosa è vera per ogni numero naturale. Esso si articola nei seguenti tre passi :
- verifica che la proporzione sia vera per n=1;
- supposizione che la proporzione sia vera per n;
- verificare che la proporzione sia vera per n+1;