Introducció

Les funcions recursives són aquelles que es criden a si mateixes per resoldre un problema. La recursió és una tècnica poderosa que permet simplificar la solució de problemes complexos dividint-los en subproblemes més petits i manejables. En aquest tema, aprendrem què són les funcions recursives, com funcionen i com utilitzar-les de manera efectiva en C.

Conceptes Clau

Funció Recursiva: Una funció que es crida a si mateixa.
Cas Base: La condició que atura la recursió.
Cas Recursiu: La part de la funció que inclou la crida recursiva.

Estructura d'una Funció Recursiva

Una funció recursiva generalment té dues parts:

Cas Base: La condició que atura la recursió per evitar un bucle infinit.
Cas Recursiu: La crida a la mateixa funció amb un argument modificat que s'acosta al cas base.

Exemple: 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 <stdio.h>

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

int main() {
    int number = 5;
    printf("Factorial de %d és %d\n", number, factorial(number));
    return 0;
}

Implementació Recursiva

#include <stdio.h>

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

int main() {
    int number = 5;
    printf("Factorial de %d és %d\n", number, factorial(number));
    return 0;
}

Explicació del Codi

Cas Base: if (n == 0) return 1;
- Quan n és 0, el factorial de 0 és 1 per definició. Això atura la recursió.
Cas Recursiu: return n * factorial(n - 1);
- La funció es crida a si mateixa amb n - 1, acostant-se al cas base.

Exercicis Pràctics

Exercici 1: Suma de Nombres Naturals

Escriu una funció recursiva que calculi la suma dels primers n nombres naturals.

Solució

#include <stdio.h>

int suma(int n) {
    if (n == 0) {
        return 0; // Cas Base
    } else {
        return n + suma(n - 1); // Cas Recursiu
    }
}

int main() {
    int number = 10;
    printf("La suma dels primers %d nombres naturals és %d\n", number, suma(number));
    return 0;
}

Exercici 2: Seqüència de Fibonacci

Escriu una funció recursiva que calculi el n-è nombre de la seqüència de Fibonacci. La seqüència de Fibonacci es defineix com:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) per n > 1

Solució

#include <stdio.h>

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

int main() {
    int number = 10;
    printf("El %d-è nombre de Fibonacci és %d\n", number, fibonacci(number));
    return 0;
}

Errors Comuns i Consells

Oblidar el Cas Base: Sense un cas base, la funció recursiva entrarà en un bucle infinit i eventualment causarà un desbordament de la pila.
Crides Recursives Incorrectes: Assegura't que els arguments de la crida recursiva s'acosten al cas base.
Optimització: Les funcions recursives poden ser ineficients per a problemes com la seqüència de Fibonacci. Considera utilitzar la memòria cau (memoització) o una solució iterativa per millorar el rendiment.

Resum

Les funcions recursives són una eina poderosa per resoldre problemes complexos dividint-los en subproblemes més petits. Hem vist com implementar funcions recursives en C, incloent exemples pràctics com el càlcul del factorial i la seqüència de Fibonacci. També hem discutit errors comuns i consells per evitar-los. Amb aquesta base, estàs preparat per aplicar la recursió a una varietat de problemes en programació.

Funcions Recursives

Introducció

Conceptes Clau

Estructura d'una Funció Recursiva

Exemple: Factorial d'un Nombre

Implementació Iterativa

Implementació Recursiva

Explicació del Codi

Exercicis Pràctics

Exercici 1: Suma de Nombres Naturals

Solució

Exercici 2: Seqüència de Fibonacci

Solució

Errors Comuns i Consells

Resum

Curs de Programació en C

Mòdul 1: Introducció al C

Mòdul 2: Tipus de Dades i Variables

Mòdul 3: Flux de Control

Mòdul 4: Funcions

Mòdul 5: Arrays i Strings

Mòdul 6: Punteres

Mòdul 7: Estructures i Unions

Mòdul 8: Assignació Dinàmica de Memòria

Mòdul 9: Gestió d'Arxius

Mòdul 10: Temes Avançats

Mòdul 11: Millors Pràctiques i Optimització

Mòdul 12: Projecte i Avaluació Final