El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Recursivitat

Següent ►
►

La recursivitat és una tècnica de programació on una funció es crida a si mateixa per resoldre un problema. Aquesta tècnica és molt útil per a problemes que es poden dividir en subproblemes més petits del mateix tipus. En aquest tema, aprendrem què és la recursivitat, com funciona, i veurem alguns exemples pràctics.

Conceptes Clau

  1. Funció Recursiva: Una funció que es crida a si mateixa.
  2. Cas Base: La condició que atura la recursió per evitar un bucle infinit.
  3. Cas Recursiu: La part de la funció que inclou la crida recursiva.

Com Funciona la Recursivitat

Quan una funció es crida a si mateixa, es crea una nova instància de la funció amb els seus propis paràmetres i variables locals. Aquest procés continua fins que es compleix el cas base, moment en què la funció comença a retornar valors i les instàncies anteriors es resolen una per una.

Exemple Bàsic: Factorial d'un Nombre

El factorial d'un nombre n (denotat com n!) és el producte de tots els nombres enters positius menors o iguals a n. Per exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Implementació Iterativa

#include <iostream>
using namespace std;

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

int main() {
    int number = 5;
    cout << "Factorial de " << number << " és " << factorial(number) << endl;
    return 0;
}

Implementació Recursiva

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) { // Cas Base
        return 1;
    } else { // Cas Recursiu
        return n * factorial(n - 1);
    }
}

int main() {
    int number = 5;
    cout << "Factorial de " << number << " és " << factorial(number) << endl;
    return 0;
}

Explicació del Codi Recursiu

  1. Cas Base: if (n <= 1) return 1;
    • Quan n és 1 o menys, la funció retorna 1, aturant la recursió.
  2. Cas Recursiu: return n * factorial(n - 1);
    • La funció es crida a si mateixa amb n - 1 fins que arriba al cas base.

Exemple Avançat: Seqüència de Fibonacci

La seqüència de Fibonacci és una sèrie de nombres on cada nombre és la suma dels dos anteriors. Els primers dos nombres són 0 i 1. La seqüència comença així: 0, 1, 1, 2, 3, 5, 8, ...

Implementació Recursiva

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) { // Cas Base
        return n;
    } else { // Cas Recursiu
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int number = 10;
    cout << "El " << number << "è nombre de Fibonacci és " << fibonacci(number) << endl;
    return 0;
}

Explicació del Codi

  1. Cas Base: if (n <= 1) return n;
    • Quan n és 0 o 1, la funció retorna n, aturant la recursió.
  2. Cas Recursiu: return fibonacci(n - 1) + fibonacci(n - 2);
    • La funció es crida a si mateixa amb n - 1 i n - 2 fins que arriba al cas base.

Exercicis Pràctics

  1. Sumar Nombres Naturals: Escriu una funció recursiva que sumi els primers n nombres naturals.
  2. Potència d'un Nombre: Escriu una funció recursiva que calculi a^b (a elevat a la potència b).
  3. Inversió d'una Cadena: Escriu una funció recursiva que inverteixi una cadena de caràcters.

Solucions

  1. Sumar Nombres Naturals
int sumaNaturals(int n) {
    if (n <= 0) {
        return 0;
    } else {
        return n + sumaNaturals(n - 1);
    }
}
  1. Potència d'un Nombre
int potencia(int a, int b) {
    if (b == 0) {
        return 1;
    } else {
        return a * potencia(a, b - 1);
    }
}
  1. Inversió d'una Cadena
#include <iostream>
#include <string>
using namespace std;

void invertirCadena(string &str, int start, int end) {
    if (start >= end) {
        return;
    }
    swap(str[start], str[end]);
    invertirCadena(str, start + 1, end - 1);
}

int main() {
    string str = "Hola, món!";
    invertirCadena(str, 0, str.length() - 1);
    cout << "Cadena invertida: " << str << endl;
    return 0;
}

Errors Comuns i Consells

  1. Oblidar el Cas Base: Sense un cas base, la funció recursiva entrarà en un bucle infinit.
  2. Desbordament de la Pila: Les funcions recursives poden consumir molta memòria si la profunditat de la recursió és massa gran.
  3. Optimització: Algunes funcions recursives poden ser optimitzades utilitzant tècniques com la memòria cau (memoization) per evitar càlculs repetits.

Resum

La recursivitat és una tècnica poderosa que permet resoldre problemes complexos de manera elegant. És important comprendre els conceptes de cas base i cas recursiu per implementar funcions recursives correctament. Amb la pràctica, podràs identificar quan és adequat utilitzar la recursivitat i com optimitzar les teves solucions per a una millor eficiència.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats