Recursión — cómo funciona, ejemplos y casos base

La recursión en matemáticas significa definir una función, una sucesión o un proceso usando casos más pequeños de la misma idea. Una definición recursiva solo funciona si incluye un caso base y una regla que haga que cada caso nuevo avance hacia ese caso base.

Si solo necesitas la idea central, es esta: la recursión deja de ser útil en el momento en que la regla de reducción ya no llega a un punto de parada válido.

Qué significa la recursión en matemáticas

Una definición recursiva no enumera cada caso por separado. En su lugar, da un punto de partida y una regla para construir casos más grandes a partir de casos más pequeños.

Eso es diferente de una fórmula directa. Una fórmula directa da la respuesta a partir de la entrada en una sola expresión. Una definición recursiva reduce el problema paso a paso hasta llegar a un caso que ya se conoce.

Por qué se necesita un caso base

El caso base es el punto de parada. Sin él, la definición sigue remitiendo a casos cada vez más pequeños sin terminar nunca.

El caso base también tiene que encajar con la regla que elegiste. Si el paso recursivo reduce de $n$ a $n-1$, entonces el caso base tiene que poder alcanzarse con ese patrón para las entradas que permites.

Ejemplo resuelto: recursión del factorial

El factorial es una definición recursiva estándar. Para números enteros $n \ge 0$, define el factorial mediante

$$0! = 1$$

y, para $n \ge 1$,

$$n! = n(n-1)!$$

Aquí, $0! = 1$ es el caso base, y $n! = n(n-1)!$ es el paso recursivo.

Para hallar $4!$, sigue reduciendo hasta que aparezca el caso base:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Ahora aplica el caso base $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Este es el patrón completo de la recursión: reducir a un caso más pequeño, llegar al caso base y luego evaluar de vuelta hasta la pregunta original.

Recursión vs. relación de recurrencia

La recursión es la idea más general. Una relación de recurrencia es una regla recursiva para una sucesión, donde cada término depende de términos anteriores.

Por ejemplo, la sucesión de Fibonacci se da mediante una recurrencia porque cada término se define a partir de términos anteriores. El factorial también es recursivo, pero normalmente se presenta como una definición recursiva de una función y no como una recurrencia de una sucesión.

Errores comunes en recursión

Omitir el caso base

Si no hay caso base, la definición no termina.

Usar un paso que no se hace más pequeño

Si el paso recursivo no avanza hacia el caso base, el proceso puede repetirse para siempre o quedar indefinido para algunas entradas.

Olvidar la condición de la regla

En el ejemplo del factorial, la regla $n! = n(n-1)!$ se usa para $n \ge 1$. Esa condición importa. Sin ella, podrías intentar aplicar la regla donde la definición no estaba pensada para usarse.

Suponer que la recursión es solo una idea de programación

La recursión aparece en matemáticas mucho antes que en el código. Es una forma de definir funciones, sucesiones y conjuntos haciendo referencia a casos más pequeños. Después, la inducción se usa a menudo para demostrar enunciados sobre esas definiciones recursivas.

Cuándo es útil la recursión

La recursión es útil cuando un problema se divide de forma natural en versiones más pequeñas de sí mismo. La ves en factoriales, sucesiones de tipo Fibonacci, conjuntos definidos recursivamente y muchos algoritmos.

Es especialmente útil cuando el caso más pequeño tiene la misma estructura que el original. Si el caso más pequeño no es realmente el mismo tipo de problema, la recursión normalmente no es la herramienta adecuada.

Una prueba rápida para una definición recursiva válida

Hazte dos preguntas:

1. ¿Tengo un caso base?
2. ¿Cada paso recursivo se acerca a él?

Si alguna respuesta es no, la definición necesita corregirse.

Prueba un problema similar

Define una sucesión mediante

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Luego halla $a_2$, $a_3$ y $a_4$. Es una forma rápida de practicar cómo identificar el caso base y el paso recursivo en un contexto nuevo.