Introducción a la recursividad

Parte de la sección Lógica y Flujo del Journey de C++ de Coddy — lección 45 de 56.

La recursividad es una técnica de programación en la que una función se llama a sí misma para resolver un problema. En lugar de utilizar bucles, las funciones recursivas descomponen problemas complejos en subproblemas más pequeños y similares hasta que alcanzan un caso sencillo que puede resolverse directamente.

Cada función recursiva debe tener dos componentes esenciales. El caso base es una condición que detiene la recursión; sin él, la función se llamaría a sí misma indefinidamente. El paso recursivo es donde la función se llama a sí misma con parámetros modificados, acercándose al caso base con cada llamada.

Aquí tienes un ejemplo sencillo de cuenta regresiva que demuestra la recursividad:

void countdown(int n) {
    if (n <= 0) {           // Caso base: detenerse cuando n llega a 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Paso recursivo: llamar con n-1
}

Cuando llamas a countdown(3), imprime 3, luego llama a countdown(2), que imprime 2, luego llama a countdown(1), y así sucesivamente hasta que alcanza el caso base. Cada llamada a la función espera a que la siguiente se complete antes de finalizar, creando una cadena de llamadas que eventualmente se deshace de regreso al llamador original.

Hoja de referencia

La recursividad es cuando una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños.

Toda función recursiva necesita:

Caso base: condición que detiene la recursividad
Paso recursivo: la función se llama a sí misma con parámetros modificados

Ejemplo de función de cuenta regresiva:

void countdown(int n) {
    if (n <= 0) {           // Caso base
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Paso recursivo
}

Pruébalo tú mismo

Esta lección no incluye un desafío de código.