# Prolog/Funzioni ricorsive

Prolog
Copertina Tutti i moduli · Sviluppo
    CopertinaProlog/Copertina
    Basi
* BasiProlog/Primi passi
* Regole
* Regole ricorsive
* Variabili
* Liste
* Matematica, Funzioni ed Uguaglianza
* Mettere il tutto assieme
* Risoluzione di un rompicapo logico
    Programmazione
* Tagli e Negazione
* Leggere e scrivere il codice
* Liste di differenza
* Grammatiche a clausole finite
* Motori di inferenza
    Argomenti avanzati
* Mappe associative
* Tecniche di ricerca
* Ordinamento
* Grafica: XPCE
    Predicati built-inProlog/Predicati built-in
* Predicati built-inProlog/Predicati built-in
* Funzioni ricorsiveProlog/Funzioni ricorsive
* Termini di collaudo
* Costrutti Bagof, Setof e Findall
* Ordinamento
* I/O
    Ulteriori risorse
* Cos'e' il Prolog?
* Storia del Prolog
* Introduzione alla logica
* Glossario
* Alcune risposte a domande comuni
* Esercizi (collegamento esterno)
    Approfondimenti
* Programmazione di ordine superiore)
* Programmazione su vincoli logici
* Grammatiche a clausole definite
* Combinazioni di linguaggi
* Selezione di alcuni argomenti interessanti tratti dagli usergroup
* Collegamenti Esterni
Modifica il sommario
Questa sezione riguarda l'uso di regole ricorsive.

## Regole ricorsive

Considera il seguente programma.
Esso mostra una linea maschile di discendenza e definisce con una regola quando qualcuno è parente diretto in secondo grado (cioè quando una persona è genitore di un genitore). Come si fa per definire se uno è antenato di una persona cioè genitore del genitore del genitore ecc. ? Procedendo nel modo tradizionale avremmo :
Chiaramente questo non sembra il modo migliore. Non è elegante, richiede un sacco di lavoro e cosa molto importante, non definisce cosa sia antenato e cosa no. Questo modo funziona per almeno quattro generazioni, ma per l'antenato diretto in quinto grado occorrebbe una nuova linea .Cio' di cui abbiamo bisogno è una definizione di antenato completa che permetta di stabilire se uno è antenato indipendentemente dalla lontananza fra le generazioni.
Per raggiungere questo obiettivo abbiamo bisogno di definire che cosa sia un antenato. Al primo rigo la persona P è antenato di C, se P è genitore di C. Inoltre dobbiamo dire che la persona A è antenato di C se la persona A è genitore di un antenato C. Queste due definizioni si completano bene a vicenda.
Per esempio, se ci chiedessimo se Steve è antenato di John, guarderemmo le definizioni. Steve non è di certo genitore di John, quindi la regola non si applica. Steve è genitore di un antenato di John? Steve è un genitore di Jim, quindi la domanda diventa, è Jim un antenato di John? Jim è un genitore di David, allora David è un antenato di John? A questo punto possiamo usare la prima definizione, perché David è un genitore di John.
In prolog, la definizione suonerebbe cosi':
La seconda regola è ricorsiva ; usa l'antenato per definire un antenato. La prima regola è chiamata stop predicate perché si ferma richiamandosi.
Quando affronta la domanda ?- ancestor(steve,john). prolog tentera' la prima linea di definizione,ma non potra' unificare parent(steve, john) con altre linee in archivio. Cerchera' allora la seconda linea con i sottoobiettivi parent(steve, X) e ancestor(X, B). Puo' unificare parent(steve, X) con parent(steve, jim), cosi' prolog ha a sinistra ancestor(jim, john). Continuera' fino a ancestor(david, john) che , usando la prima linea della definizione è vera perché parent(david, john) è vera.
Prolog è comodo quando si tratta di definizioni ricorsive. Esso puo' trovare tranquillamente tutti gli antenati di John:
O tutte e persone di cui Nathan è antenato:

## Usare regole ricorsive

Usare regole ricorsive comporta dei pericoli, puo' portare ad ogni tipo di loop, i quali causano solitamente degli stack overflows, cioè che prolog ha esaurito la memoria. Le seguenti linee dovrebbero essere tenute a mente durante la scrittura di regole ricorsive.
* Parti con il predicato di stop.
    Poni sempre all' inizio il predicato di stop prima del predicato ricorsivo.
* Evitare la ricorsione a sinistra
    Scrivere sempre la regola ricorsiva sulla destra.Per esempio usare:
    invece di
    Questo è lo stesso principio usato in precedenza , lascia che prolog valuti prima gli obiettivi non ricorsivi. Se fai ricorsione prima di aver valutato tutti gli obiettivi finirai in ricorsione infinita o farai un sacco di lavoro non necessario . Qualche volta è necessario porre l'elemento ricorsivo a sinistra ma fallo sapendo cio' che fai : eviterai conseguenze spiacevoli.

## Esempi

* Un classico esempio di funzione ricorsiva è il fattoriale (vedi il capitolo Matematica, Funzioni e uguaglianza). In molti linguaggi di programmazione, potresti imparare la ricorsione scrivendo una funzione fact, che prende come input un intero e rende un altro intero. In Prolog , dal momento che usiamo predicati al posto di funzioni, definiremo invece un predicato fact(X,Y) equiivalente all' affermazione "Il fattoriale di X è Y." allora, per trovare il fattoriale di 7, per esempio, useremo il simbolo query ?- fact(7,X). Prolog rispondera': X=5040.
* Una cosa che puo' essere facilmente definita come ricorsiva è una lista. In questo contesto considereremo una lista come una collezione di cose (elementi) che sono posti in un ordine ben preciso.Per definirla in modo ricorsivo, affermeremo che una lista è un singolo elemento,che è seguito da una lista. Per terminare la ricorsione abbiamo bisogno di una seconda affermazione, che sancisce una lista è qualcosa che consiste di un elemento. insieme, queste due definizioni completano una definizione di lista.
    Le liste sono utilizzate comunemente in prolog e sono usate in modo ricorsivo. Il seguente capitolo spiega come.