Recursión

La recursión es un método en el que algo se define haciendo referencia a sí mismo. En matemáticas, esto significa que un nuevo término en una sucesión, una función o un conjunto depende de pasos anteriores. De este modo, se pueden construir estructuras complejas a partir de un inicio sencillo.

 

Un ejemplo simple es una sucesión definida recursivamente:

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

El punto de partida es \( \large a_{0} = 1 \). Cada nuevo término se obtiene multiplicando el anterior por 2. Así, los primeros valores son

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

Forma recursiva y explícita

Una fórmula recursiva describe un término a partir de los anteriores. A menudo también se puede encontrar una fórmula explícita, donde cada término se calcula directamente sin conocer los previos. Para el ejemplo anterior se cumple

 

$$ \large a_{n} = 2^n $$

 

Las definiciones recursivas son buenas para mostrar una estructura, mientras que las fórmulas explícitas son rápidas para calcular. Ambos enfoques son útiles y están estrechamente relacionados.

 

Sucesiones

La recursión se usa para definir muchas sucesiones conocidas. Por ejemplo, la sucesión de Fibonacci, donde cada término es la suma de los dos anteriores.

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Funciones

Otro ejemplo es la función factorial. Se puede definir recursivamente como

 

$$ \large n! = n \cdot (n-1)!, \quad 0! = 1 $$

 

Conjuntos

Los conjuntos también pueden definirse recursivamente. Si comenzamos diciendo que 3 pertenece al conjunto y luego añadimos la suma de elementos ya conocidos, obtenemos todos los números divisibles por 3. Esto puede escribirse como una definición recursiva:

 

$$ \large 3 \in M, \quad x \in M \;\Rightarrow\; x + 3 \in M $$

 

Triángulo de Pascal

Un ejemplo geométrico conocido es el triángulo de Pascal. Cada número se forma recursivamente como la suma de los dos números superiores. Esto da una estructura triangular que contiene los coeficientes binomiales.

 

$$ \large
\begin{array}{cccccccccccccccccc}
        &       &       &       &       &       &       &       & 1     &       &       &       &       &       &       &       \\
        &       &       &       &       &       &       & 1     &       & 1     &       &       &       &       &       &       \\
        &       &       &       &       &       & 1     &       & 2     &       & 1     &       &       &       &       &       \\
        &       &       &       &       & 1     &       & 3     &       & 3     &       & 1     &       &       &       &       \\
        &       &       &       & 1     &       & 4     &       & 6     &       & 4     &       & 1     &       &       &       \\
        &       &       & 1     &       & 5     &       & 10    &       & 10    &       & 5     &       & 1     &       &       \\
        &       & 1     &       & 6     &       & 15    &       & 20    &       & 15    &       & 6     &       & 1     &       \\
        & 1     &       & 7     &       & 21    &       & 35    &       & 35    &       & 21    &       & 7     &       & 1     \\
  1     &       & 8     &       & 28    &       & 56    &       & 70    &       & 56    &       & 28    &       & 8     &       & 1 \\
\end{array}
$$

 

 

Aplicación

La recursión es una herramienta fundamental en matemáticas discretas. Se usa para describir procesos infinitos, demostrar propiedades con inducción y construir algoritmos. En geometría, la recursión también juega un papel, por ejemplo en la construcción de fractales.

 

Relación con la inducción

Al trabajar con definiciones recursivas, la inducción es una herramienta natural de demostración. Primero se muestra que una afirmación vale en el caso base y luego que se cumple de un paso al siguiente. Así se pueden demostrar propiedades de toda la estructura infinita definida recursivamente.