La recursió és una tècnica de programació on una funció es crida a si mateixa per resoldre un problema. Aquesta tècnica és especialment útil per resoldre problemes que es poden dividir en subproblemes més petits del mateix tipus. En aquesta secció, explorarem els conceptes bàsics de la recursió, veurem alguns exemples pràctics i practicarem amb exercicis.
Conceptes Bàsics de la Recursió
Definició
Una funció recursiva és una funció que es crida a si mateixa dins del seu propi cos. Perquè una funció recursiva funcioni correctament, ha de tenir dues parts essencials:
- Cas base: La condició que atura la recursió. Sense un cas base, la funció continuaria cridant-se indefinidament, causant un desbordament de la pila (stack overflow).
- Pas recursiu: La part de la funció que divideix el problema en subproblemes més petits i crida la funció recursiva amb aquests subproblemes.
Exemple Bàsic: Factorial
El factorial d'un nombre enter positiu n (denotat com n!) és el producte de tots els enters positius menors o iguals a n. Per exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120.
La definició recursiva del factorial és:
0! = 1(cas base)n! = n * (n-1)!per an > 0(pas recursiu)
Implementació en Python
def factorial(n):
if n == 0:
return 1 # Cas base
else:
return n * factorial(n - 1) # Pas recursiu
# Exemple d'ús
print(factorial(5)) # Sortida: 120Traça de l'Execució
Per entendre millor com funciona la recursió, vegem la traça de l'execució de factorial(3):
factorial(3)cridafactorial(2)factorial(2)cridafactorial(1)factorial(1)cridafactorial(0)factorial(0)retorna1(cas base)factorial(1)retorna1 * 1 = 1factorial(2)retorna2 * 1 = 2factorial(3)retorna3 * 2 = 6
Exemples Pràctics
Suma de Números Naturals
La suma dels primers n números naturals es pot definir recursivament com:
sum(0) = 0(cas base)sum(n) = n + sum(n-1)per an > 0(pas recursiu)
Implementació en Python
def suma_numeros(n):
if n == 0:
return 0 # Cas base
else:
return n + suma_numeros(n - 1) # Pas recursiu
# Exemple d'ús
print(suma_numeros(5)) # Sortida: 15Seqüència de Fibonacci
La seqüència de Fibonacci es defineix com:
F(0) = 0(cas base)F(1) = 1(cas base)F(n) = F(n-1) + F(n-2)per an > 1(pas recursiu)
Implementació en Python
def fibonacci(n):
if n == 0:
return 0 # Cas base
elif n == 1:
return 1 # Cas base
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Pas recursiu
# Exemple d'ús
print(fibonacci(6)) # Sortida: 8Exercicis Pràctics
Exercici 1: Potència d'un Nombre
Escriu una funció recursiva potencia(base, exponent) que calculi la potència d'un nombre. Per exemple, potencia(2, 3) ha de retornar 8.
Solució
def potencia(base, exponent):
if exponent == 0:
return 1 # Cas base
else:
return base * potencia(base, exponent - 1) # Pas recursiu
# Exemple d'ús
print(potencia(2, 3)) # Sortida: 8Exercici 2: Inversió d'una Cadena
Escriu una funció recursiva invertir_cadena(cadena) que inverteixi una cadena de caràcters. Per exemple, invertir_cadena("hola") ha de retornar "aloh".
Solució
def invertir_cadena(cadena):
if len(cadena) == 0:
return "" # Cas base
else:
return cadena[-1] + invertir_cadena(cadena[:-1]) # Pas recursiu
# Exemple d'ús
print(invertir_cadena("hola")) # Sortida: "aloh"Errors Comuns i Consells
- Oblidar el cas base: Sense un cas base, la funció recursiva continuarà cridant-se indefinidament, causant un desbordament de la pila.
- No reduir el problema: Assegura't que cada crida recursiva redueixi el problema d'alguna manera, acostant-se al cas base.
- Utilitzar recursió quan no és necessari: La recursió pot ser elegant, però no sempre és la solució més eficient. Per a problemes simples, una solució iterativa pot ser més adequada.
Resum
En aquesta secció, hem après què és la recursió i com utilitzar-la per resoldre problemes. Hem vist exemples pràctics com el càlcul del factorial, la suma de números naturals i la seqüència de Fibonacci. També hem practicat amb exercicis per reforçar els conceptes apresos. La recursió és una eina poderosa en la programació, però cal utilitzar-la amb cura per evitar errors comuns.
Fonaments de la Programació
Mòdul 1: Introducció a la Programació
- Què és la programació?
- Història de la programació
- Llenguatges de programació
- Entorns de desenvolupament