Algoritmos en C/C++

La recursividad y la pila de llamadas en C y C++

En esta lección vas a calcular un factorial con una función recursiva y a entender el caso base y el coste en memoria de la recursividad.

Introducción

La recursividad consiste en resolver un problema reduciéndolo a otro más pequeño del mismo tipo. Toda función recursiva necesita un caso base (base case), y cada llamada debe acercarse a él; si no, el programa vuelve a llamar a la función sin fin.

Puntos importantes

Prueba con una entrada vacía, un solo elemento, valores repetidos y datos ya ordenados.
Primero haz que el código sea correcto y después optimízalo.
En código real, usa preferentemente las funciones ya hechas de la biblioteca estándar.

Mira cómo funciona

Pulsa Paso para seguir cada llamada. Las llamadas nuevas entran en la pila de llamadas y cada una devuelve su valor a quien la hizo.

Ejemplos de código C y C++

Ejecutar →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Resultado de la ejecución

C++

Ejecutar →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Resultado de la ejecución

Comparación entre C y C++

La función factorial devuelve 1 cuando number es menor que 2, que es el caso base, y si no devuelve number * factorial(number - 1). Cada llamada ocupa un poco más de espacio en la pila de llamadas (call stack), así que el algoritmo usa O(n) de tiempo y O(n) de pila. La versión de C++ marca la función como constexpr, así que el valor puede calcularse ya al compilar. Con entradas grandes hay que validar los datos y, en general, es mejor usar un bucle que la recursividad.

Los bucles, los punteros, las longitudes y los búferes temporales se escriben de forma explícita.

C++

Los iteradores y los algoritmos estándar separan el procesamiento de la forma en que se guardan los datos.

Ejercicios de práctica

Ejecuta las dos versiones y después modifica el código para ver la diferencia de seguridad que aporta cada lenguaje.

Sigue cada comparación en papel.
Prueba con valores repetidos y con valores muy grandes y muy pequeños.
Mide el tiempo de ejecución de tu código y compáralo con la biblioteca estándar.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos