Recursión

Definiciones recursivas

El factorial

El factorial de un natural $n$ es el producto de los naturales de 1 a $n$: $n! = 1 \cdot 2 \cdots n$, con la convención $0! = 1$. Los puntos suspensivos de esa fórmula esconden un bucle, y la clase Bucles enseñó a escribirlo. Ahora bien, la misma definición admite otra forma, que no menciona ningún bucle: el factorial de $n$ es $n$ veces el factorial de $n - 1$, y el de 0 es 1.

Esta es una definición recursiva: define el factorial de $n$ por medio del factorial de un número menor. No es circular, porque cada aplicación de la segunda regla baja un escalón y la escalera termina en la primera: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Las dos reglas tienen nombre. La primera es el caso base, que da el resultado sin referirse a nada más; la segunda es el caso recursivo, que reduce el problema a una instancia menor del mismo problema.

C++ permite que una función se llame a sí misma, y con ello la definición se traduce casi palabra por palabra.

#include <print>​// Factorial de n.// Precondición: 0 <= n <= 12 (la cota se justifica más adelante).// Poscondición: devuelve n! = 1 · 2 · ... · n, con 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // caso base    }    return n * factorial(n - 1);    // caso recursivo}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

El contrato no es decorativo: con $n = -1$ el caso recursivo llamaría con $-2$, después con $-3$, y nunca alcanzaría el 0; y $13!$ no cabe en un int. Muchos textos introductorios escriben este factorial con el caso base if (n == 0 | n == 1)|, redundante pero inofensivo, y sin decir nada de los negativos ni del tamaño del resultado: su código no termina con $n < 0$ y da un resultado sin sentido desde $13!$. Ambos defectos se examinarán en su sección.

Caso base y caso recursivo

Toda función recursiva tiene uno o varios casos base, que se resuelven directamente, y uno o varios casos recursivos, que llaman a la misma función con un argumento menor en algún sentido preciso y combinan lo que devuelve.

La potencia $x^n$, con $n$ natural, se define por $x^0 = 1$ y $x^n = x \cdot x^{n - 1}$: el tamaño es el exponente. La suma de las cifras de un natural $n$ (la de 2026 es $2 + 0 + 2 + 6 = 10$) se define así: si $n < 10$, la suma es $n$, porque tiene una sola cifra; si no, es la suma de las cifras de $\lfloor n / 10 \rfloor$, que es $n$ sin su última cifra, más esa última cifra, $n \bmod 10$. Aquí el tamaño es el número de cifras.

#include <print>​// x elevado a n. Precondición: n >= 0.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Suma de las cifras decimales de n. Precondición: n >= 0.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("suma de las cifras de 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375suma de las cifras de 2026: 10

Escribir una función recursiva consiste, por tanto, en responder dos preguntas: qué casos se resuelven sin ayuda, y cómo se obtiene la solución de un caso a partir de la de uno menor. Si ambas respuestas son correctas, la función lo es, y la sección siguiente lo demuestra.