La recursió és un concepte fonamental en la programació, especialment en Prolog. En aquest tema, aprendrem què és la recursió, com es pot implementar en Prolog i veurem alguns exemples pràctics. També proporcionarem exercicis per reforçar els conceptes apresos.
Què és la Recursió?
La recursió és una tècnica de programació on una funció es crida a si mateixa per resoldre un problema. En Prolog, la recursió és sovint utilitzada per processar estructures de dades com llistes o arbres.
Conceptes Clau
- Cas Base: La condició que atura la recursió.
- Cas Recursiu: La part de la funció que crida a si mateixa.
Implementació de la Recursió en Prolog
En Prolog, la recursió es pot implementar definint una regla que es crida a si mateixa. Vegem un exemple senzill per calcular el factorial d'un nombre.
Exemple: Factorial
% Cas Base: El factorial de 0 és 1
factorial(0, 1).
% Cas Recursiu: El factorial de N és N * factorial(N-1)
factorial(N, F) :-
N > 0,
N1 is N - 1,
factorial(N1, F1),
F is N * F1.Explicació del Codi
-
Cas Base:
factorial(0, 1).- Defineix que el factorial de 0 és 1.
-
Cas Recursiu:
factorial(N, F) :-N > 0: Assegura que N és positiu.N1 is N - 1: Calcula el valor de N-1.factorial(N1, F1): Crida recursiva per calcular el factorial de N-1.F is N * F1: Calcula el factorial de N multiplicant N pel factorial de N-1.
Exemples Pràctics
Exemple 1: Suma d'una Llista
% Cas Base: La suma d'una llista buida és 0
sum_list([], 0).
% Cas Recursiu: La suma d'una llista és el primer element més la suma del resta de la llista
sum_list([H|T], Sum) :-
sum_list(T, SumT),
Sum is H + SumT.Exemple 2: Longitud d'una Llista
% Cas Base: La longitud d'una llista buida és 0
list_length([], 0).
% Cas Recursiu: La longitud d'una llista és 1 més la longitud del resta de la llista
list_length([_|T], Length) :-
list_length(T, LengthT),
Length is LengthT + 1.Exercicis Pràctics
Exercici 1: Producte d'una Llista
Escriu una funció recursiva en Prolog per calcular el producte de tots els elements d'una llista.
% Cas Base: El producte d'una llista buida és 1
product_list([], 1).
% Cas Recursiu: El producte d'una llista és el primer element multiplicat pel producte del resta de la llista
product_list([H|T], Product) :-
product_list(T, ProductT),
Product is H * ProductT.Exercici 2: Invertir una Llista
Escriu una funció recursiva en Prolog per invertir una llista.
% Cas Base: La inversió d'una llista buida és una llista buida
reverse_list([], []).
% Cas Recursiu: La inversió d'una llista és la inversió del resta de la llista amb el primer element afegit al final
reverse_list([H|T], Reversed) :-
reverse_list(T, ReversedT),
append(ReversedT, [H], Reversed).Errors Comuns i Consells
- Oblidar el Cas Base: Sense un cas base, la recursió no s'aturarà mai, causant un bucle infinit.
- No Actualitzar Correctament els Paràmetres: Assegura't que els paràmetres es modifiquen correctament en cada crida recursiva.
- Utilitzar
isCorrectament: Recorda queiss'utilitza per avaluar expressions aritmètiques.
Resum
En aquesta secció, hem après què és la recursió i com implementar-la en Prolog. Hem vist exemples pràctics com el càlcul del factorial, la suma d'una llista i la longitud d'una llista. També hem proporcionat exercicis per practicar la recursió. La recursió és una eina poderosa en Prolog que permet resoldre problemes complexos de manera elegant i eficient.
Curs de Programació en Prolog
Mòdul 1: Introducció a Prolog
- Què és Prolog?
- Instal·lant Prolog
- Primers Passos en Prolog
- Sintaxi i Estructura Bàsiques
- Fets, Regles i Consultes
Mòdul 2: Programació Bàsica en Prolog
Mòdul 3: Estructures de Dades en Prolog
Mòdul 4: Programació Avançada en Prolog
- Unificació Avançada
- Tall i Negació
- Meta-Programació
- Gramàtiques de Claus Definides (DCGs)
- Programació Lògica amb Restriccions
Mòdul 5: Prolog en la Pràctica
- Entrada/Sortida de Fitxers
- Depuració de Programes Prolog
- Biblioteques Prolog
- Interfície amb Altres Llenguatges
- Construint una Aplicació Prolog