Una definición recursiva o una definición inductiva define una entidad en términos de sí misma (es decir, recursivamente ), aunque de una manera útil. Para que esto sea posible, la definición en cualquier caso dado debe estar bien fundamentada , evitando la regresión infinita .
La mayoría de las definiciones recursivas tienen tres bases: una base, una expresión inductiva y una expresión extrema.
La diferencia entre una definición cíclica y una definición recursiva es que esta última debe tener casos base que satisfagan la definición sin estar definidos en términos de la definición misma, y todos los demás casos cubiertos por la definición deben ser "menos" ( más cercanos a esos casos base ). casos que rompen la recursividad).
Por el contrario, una definición cíclica no tiene casos base y se define a sí misma en términos de sí misma y no como una versión de sí misma más cercana a la clase base. Esto conduce a un círculo vicioso . Entonces, una broma como "Definición recursiva: ver Definición recursiva " es incorrecta: en realidad es una definición cíclica.
Los números primos se pueden definir como:
El entero 2 es nuestro caso base; probar la primalidad de cualquier número mayor X requiere que conozcamos la primalidad de cada número entero entre X y 2, pero cada uno de esos números está más cerca del caso base 2 que X.
Los números pares se pueden definir como formados por
Ejemplos: