Usamos la recursión para expresar tales funciones o programas. La recursión es un tipo especial de composición donde la función definible en sí misma se compone con algo más para definirse. Puede que se escuche raro ortorreado en la primera vez. Veremos alguna definición análoga en nuestra sociedad para entender su poder.
Pero imagina una simple definición de humano (según el Corán y la Biblia):
Aquí humano se define a partir de la definición de otro humano y se llama recursión o inducción. En la definición de recursividad (o inducción), debe haber al menos un punto base para el ejemplo «Adán fue humano y Eva fue humana «.
Tomemos otro ejemplo, la definición de los números naturales. Supongamos que tenemos todo tipo de números en nuestro conocimiento incluyendo números reales, números complejos, etc. Necesitamos definir el número natural. Aquí está la definición simple – 0 es un número natural y n+1 es un número natural si n es un número natural. Podemos usarlo para escribir una función para saber si un número es natural
12345{hbox{em isNatural}}(x)=inicio{casos*} {hbox{em true}}& cuando `x=0` {hbox{em false}}& cuando `x<0` {hbox{em isNatural}}(x-1) & de lo contrario terminar{casos*}Del mismo modo podemos escribir otra función para distinguir un ashumano animal:
123456{hbox{em isHumano}}(x)=begin{dcases*} {hbox{em true}}& cuando `x=` {em Adam} {hbox{em true}}& cuando `x=` {em Eve} {hbox{em false}}& cuando `x=` {em Amoeba} (madre de }x) & de lo contrario termina.
Dice, x es un humano si x es Adán o Eva . x no es humano si x es Amiba . Además x es también humano si y sólo si la madre de x es también humana. Bueno, en el proceso real, para justificar a un animal como humano, necesitamos conocer el árbol genealógico total de Adán y Eva lo cual es muy poco realista. Pero la definición en sí misma es muy intuitiva.
En matemáticas e informática, este estilo recursivo de definición expresa a menudo un hecho de manera muy simple e intuitiva, lo que ayuda a formalizar un algoritmo o programa de manera muy efectiva.
Para crear una definición recursiva de una función, necesitamos olvidarnos de cómo funciona realmente. Simplemente necesitamos saber si la definición es correcta matemáticamente.
Para una fácil construcción de la definición, aquí nos gustaría presentar un consejo. Debemos recordar que la función tiene uno (o más) parámetro(s) de conducción.
-
Casos base parte Necesidad de determinar el valor de la función para el caso o casos base de los parámetros de conducción. Por ejemplo, exp(n,x)=1cuando x=0.
-
Parte de recursividadLa propia función aparecerá con un valor o tamaño más pequeño (típicamente un paso) de los parámetros de conducción. Por ejemplo, exp(x-1). Esto se denomina hipótesis de inducción (HI). La hipótesis de inducción a menudo necesita ser calculada con algo más para ser igual a la definición original. Por ejemplo, exp(x)=x veces exp(x-1).Otros parámetros permanecen iguales en la recursividad llamada dentro del cuerpo.
Si seguimos los pasos anteriores, nos ayudará a construir una definición recursiva. Pronto exploraremos algunos ejemplos. En algunos ejemplos, veremos cómo se construye la función a partir de los consejos anteriores. También veremos si la definición es correcta.