5.2 Recursividad 5.2.1 Definiciones 5.2.2 Funciones recursivas

5.2 Recursividad
5.2.1 Definiciones
5.2.2 Funciones recursivas
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.
3.- 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
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 If a = 0 the mcd (a,b):=b
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, ….