La ricorsone è quando definiamo qualcosa in termini di se stesso, riutilizzando la definizione.

In che casi funziona ?

Dipende da dove ci si trova e cosa si applica.

• Ci sono infatti dei casi dove, applicare la ricorsione non porta a nulla,
• Ci sono altri casi dove, applicando la ricorsione si ottiene un risultato diverso ad ogni chiamata.

Cose da valutare in una Ricorsione:

• Cose definire in termini di se stessa
• Ricorsione che funziona (Ben formata)
• Induzione sulla ricorsione:
  • clausola base: definita immediatamente per alcuni elementi “minimali”
  • clausola induttiva: definita in termini di se stessa, ma solo per elementi “minori”

Definizioni ricorsive

Una definizione ricorsiva (non induttiva), descrive una relazione, che può:

• Definire una funzione
• Definire una funzione parziale (non totale, su alcuni valori non restituisce un risultato)
• Definire una relazione non univalente

Definizione ben data