5.2.1.- DEFINICIONES
1.- Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
2.- Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas. 3.- La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial. 4.- Un algoritmo se llama recursivo si resuelve un problema reduciéndolo a un caso del mismo problema con cada dato de entrada más pequeño. 5.- La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados. Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples. 5.2.2 Funciones recursivas Las funciones recursivas o también conocidas como funciones recursivas-μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en teoría de la computabilidad se demuestra que las funciones recursivas son precisamente las funciones que pueden ser calculadas con el formalismo de cómputo más general conocido como lo son las máquinas de Turing. Las funciones recursivas están relacionadas con las funciones primitivas recursivas y su definición inductiva se construye basándose en la de las funciones primitivas recursivas (estas se obtienen por medio de recursión primitiva y composición de funciones iniciales). No toda función recursiva es primitiva recursiva Ejemplos 1.- Suponemos que f se define recursivamente como f(0) = 3 f(n+1) = 2f(n)+3 Obtén f(1), f(2), f(3) y f(4) Solución: a partir de la definición recursiva se obtiene que: f(1)=2f(0)+2=2.3+3=9 f2=2f(1)+3+2.9+3=21 f(3)=2f(2)+3=2.21+=45 f(4)=2f(3)+3=2.45+3=93 Muchas funciones se pueden estudiar utilizando sus definiciones recursivas. La función factorial es un ejemplo de estas funciones. 2.- Da una definición recursiva de an donde a es el número real no nulo y n es un entero no negativo Solución: la definición recursiva contiene dos partes. Primero se especifica a0 mediante 20=1. Luego se da una regla para encontrar an+1 a partir de an estos es an+1 = a.an para n = 0,1,2,3… estas dos igualdades definen an de una forma única para n entero no negativo. 3.- Obtén los números de fabonacci f2, f3, f4, f5 y f6 Solución: de la primera parte de la definición se sabe que f0=0 y f1 = 0. De la segunda se deduce que F2 = f1 +f0 = 1 + 0 =1 F3 = f2 + f1 = 1+1 =2 F4= f3 + f2 = 2 +1 = 3 F5 = f4 +f3 = 3 +2 =5 F6 = f5 + f4 = 5 +3 = 8 Podemos utilizar la definición recursiva de los números de fabonacci para demostrar mucha de sus propiedades. 5.2.3 ALGORITMOS RECURSIVOS Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente. Recursividad indirecta Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y estas se llaman unas a otras formando ciclos se dice que la recursión es indirecta. Ejemplo 1.- Da un algoritmo recursivo para hallar an, donde a es el número real distinto de cero y n un entero no negativo. Solución: Podemos construir un algoritmo recursivo basándonos en la definición recursiva de an. Esta definición afirma que an+1 = a.an para n > 0 con la condición inicial a0 = 1. Para calcular an podemos usar sucesivamente la regla recursiva para reducir el exponente hasta que se haga cero
Algoritmo 1 un algoritmo recursivo para hallar an
Procedure potencia (a número real no nulo, n: entero no negativo)
If n = 0 the potencia (a,n):=1
Else potencia (a,n):=a.potencia (a,n-1)
2.- Da un algoritmo recursivo para calcular el máximo común divisor de dos enteros no negativos a y b, a > b.
Solución: nos podemos basar en la reducción mcd(a, b) = mcd (b mod a, a) y la condición mcd (0,b) = b cuando b > 0.
Algoritmo 2 un algoritmo recursivo para hallar el mcd (a, b)
Procedure mcd(a, b: entero no negativo, a
Else mcd (a, b):=mcd (b mod a,a)
3.- Expresa el algoritmo de búsqueda lineal como procedimiento recursivo
Solución: para buscar x en la sucesión a1, a2 …an en el paso decimo comparamos x y ai. Si x = a entonces i es la posición de x. es el caso contrario la búsqueda de x se reduce a buscar en la sucesión con un elemento menos es decir la sucesión ai + 1, …..an.
Algoritmo 3 un algoritmo recursivo de búsqueda lineal
Procedure búsqueda (i, j, x)
If ai = x the
Posicion :=i
Else if i = j the
Posicion :=0
Else busqueda (i+ 1, j, x
4.- El procedimiento recursivo del algoritmo 4 de el valor de n! cuando la entrada en un entero positivo n
Algoritmo 4 un algoritmo recursivo para la función factorial
Procedure factorial (n: entero positivo)
If n= 1 the
Factorial (n) :=1
Else factorial (n) :n. factorial (n-1)
5.-
Algoritmo 5 un algoritmo recursivo para los números de fibonacci
Procedure fibonacci (n entero no negativo)
If n= 0 the Fibonacci (0) = 0
Else if n = 1 the Fibonacci(1) = 1
Else Fibonacci (n) = Fibonacci (n-1)+ Fibonacci (n-2)
Un algoritmo se llama recursivo si resuelve un problema reduciéndolo a un caso del mismo problema con cada dato de entrada más pequeño
Funciones
Los números de fabanacci, f0, f1, f2…. De definen a partir de las ecuaciones f0 = 0, f1 = 1 y fn = fn-1 + f n-2
Para n = 2, 3, 4, ….
No hay comentarios:
Publicar un comentario