Recursión en C

La recursión es una técnica en la que una función se llama a sí misma para resolver un problema.

En esta lección, aprenderá:

• Qué es la recursión y cómo funciona.
• Cómo implementar funciones recursivas.
• La diferencia entre recursión e iteración.

¿Qué es la recursión?

La recursión ocurre cuando una función se llama a sí misma para resolver una parte más pequeña de un problema.

Sintaxis de ejemplo:

void function() { function(); // Recursive call }

Toda función recursiva debe tener un caso base para evitar la recursión infinita.

Ejemplo: recursión

Este programa muestra la recursión al imprimir los números del 5 al 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Caso base de la recursión

Una función recursiva debe incluir un caso base para detener la recursión.

Ejemplo:

if (n == 0) return;

Sin un caso base, la función se llamará a sí misma indefinidamente, lo que provocará un desbordamiento de pila.

Ejemplo: factorial mediante recursión

Este programa calcula el factorial de un número mediante recursión.

#include <stdio.h>

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

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Recursión frente a iteración

La recursión y la iteración (los bucles) pueden producir los mismos resultados, pero funcionan de manera diferente.

Diferencias:

• La recursión utiliza llamadas a funciones y requiere más memoria.
• La iteración utiliza bucles y, por lo general, es más eficiente.
• La recursión simplifica el código en problemas como el recorrido de árboles.

Ejemplo: secuencia de Fibonacci (recursiva)

Este programa calcula la secuencia de Fibonacci mediante recursión.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

¿Cuándo usar la recursión?

La recursión resulta útil para problemas que implican:

• Recorridos de árboles.
• Retroceso (por ejemplo, para resolver laberintos).
• Problemas matemáticos, como el factorial y Fibonacci.

Resumen

En esta lección, ha aprendido:

• Qué es la recursión y cómo funciona.
• La importancia de un caso base.
• La diferencia entre recursión e iteración.

A continuación, exploraremos los arrays y las cadenas en C.