Le tre leggi della Ricorsione¶

Tutti gli algoritmi ricorsivi devono obbedire alle seguenti tre leggi:

1. Un algoritmo ricorsivo devo chiamare se stesso, ricorsivamente.
2. Un algoritmo ricorsivo deve avere un caso base.
3. Un algoritmo ricorsivo deve cambiare il suo stato e avvicinarsi al caso base.

Il caso base è la condizione che permette all’algoritmo di fermare la ricorsione.

• Un caso base è tipicamente un problema sufficientemente piccolo da essere risolto direttamente.
• Nell’algoritmo del fattoriale il caso base è n=1.

Dobbiamo cambiare lo stato per avvicinarci al caso base.

• Un cambio dello stato significa cambiare qualche dato che l’algoritmo sta usando.
• Di solito, questi dati diventano più piccoli in un certo senso.
• Per esempio nel fattoriale n diminuisce.