tecnologia
Recursividad
BENEMERITA UNIVERSIDAD AUTONOMA DE PUEBLA
M.C. Luz A. Sánchez Gálvez
Dominios definidos inductivamente
Los datos que se manipulan por un programa
pertenecen a undominio definido inductivamente.
Un dominio de este tipo tiene la propiedad de que el
conjunto de sus elementos se puede caracterizar de
la siguiente manera:
uno o más elementos (unnúmero finito) pertenecen al
dominio;
una o más reglas que permiten obtener uno o más
elementos del dominio de un nuevo elemento del
dominio.
Dominios definidos inductivamente
Ejemplos
Númerosnaturales:
0 es un número natural;
si n es un número natural, entonces el sucesor de n
es un número natural;
de otro modo es un número natural.
Cadenas:
la cadena vacía "" es una cadena;
Sis es una cadena, entonces, añadiendo un carácter
en la primera posición de s, se obtiene una cadena;
de otro modo no es una cadena.
Dominios definidos inductivamente
Ejemplos
Archivos detexto:
el archivo vacío es un archivo de texto;
Si a es un archivo de texto y, después, se coloca al
inicio de a una nueva línea, se obtiene un archivo de
texto;
de otro modo, no es un archivo detexto.
Recursividad
Un método es recursivo si contiene una activación
(llamada o invocación) de sí mismo (ya sea
directamente o indirectamente a través de la
activación de otrosmétodos).
Algunas funciones matemáticas con números
naturales se definen inductivamente, aprovechando el
hecho de que estas funciones operan sobre los
elementos de un dominio definido inductivamente.Recursividad
Factorial
n! = n * (n – 1)!
1,
0! = 1 y
1!= 1 * 0!
si n = 0 (caso base)
fac(n) =
n * fac(n − 1), si n > 0 (caso recursivo)
Recursividad
La definición recursivade una función refleja la
estructura de la definición inductiva del dominio en el
que opera la función, por tanto se tiene:
uno (o más) casos base, dónde el resultado de la
función se...
Regístrate para leer el documento completo.