Definiciones recursivas

Una definición recursiva es una manera de describir un objeto matemático refiriéndose a sí mismo. Para que tal definición tenga sentido, siempre debe incluir dos partes:

 

• Base: el o los primeros pasos que inician el proceso.
• Paso recursivo: una regla que explica cómo formar nuevos elementos a partir de los anteriores.

 

 

Funciones

Un ejemplo clásico es la función factorial. Aquí están la base y el paso recursivo:

 

$$ \large 0! = 1 $$

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

 

La base indica el valor de \( \large 0! \). Luego el paso recursivo describe cómo calcular \( \large n! \) a partir de \( \large (n-1)! \). De este modo, se pueden encontrar todos los valores del factorial paso a paso.

 

Ejemplo

Podemos calcular los primeros valores:

 

$$ \large 0! = 1 \quad \text{(base)} $$

$$ \large 1! = 1 \cdot 0! = 1 $$

$$ \large 2! = 2 \cdot 1! = 2 $$

$$ \large 3! = 3 \cdot 2! = 6 $$

$$ \large 4! = 4 \cdot 3! = 24 $$

 

Cada paso se construye directamente sobre el anterior, hasta llegar al valor deseado.

 

 

Funciones sobre cadenas

Las definiciones recursivas también pueden aplicarse a cadenas de símbolos. Un ejemplo es la función \( \large L(s) \), que indica la longitud de una cadena \( \large s \):

 

$$ \large L(\varepsilon) = 0 $$

$$ \large L(x \cdot s) = 1 + L(s) $$

 

Aquí \( \large \varepsilon \) significa la cadena vacía, y \( \large x \cdot s \) es una cadena formada por un primer símbolo \( \large x \) seguido del resto \( \large s \). La base dice que la cadena vacía tiene longitud 0, y el paso recursivo dice que la longitud de una cadena más larga se obtiene sumando 1 a la longitud del resto.

 

 

Resumen

Una definición recursiva siempre se construye a partir de un punto de inicio claro y una regla para avanzar. Esta división en base y paso recursivo permite construir estructuras complejas de manera precisa y sistemática. Ya sea con números, cadenas o figuras geométricas, las definiciones recursivas son una herramienta fundamental.