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, ….

5.1.- INDUCCIÓN MATEMÁTICA

5.1.- INDUCCIÓN MATEMÁTICA
En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:
Premisa mayor: El número entero tiene la propiedad .
Premisa menor: El hecho de que cualquier número entero tenga la propiedad implica que también la tiene (que se anota ).
Conclusión: Todos los números enteros a partir de tienen la propiedad .


5.1.1 PRINCIPIO DE INDUCCIÓN MATEMÁTICA

La inducción matemática se usa a menudo para verificar o probar, una conjetura obtenida mediante inducción no matemática. Hablando con precisión, el axioma de inducción dice: si M es un conjunto de enteros positivos, con las siguientes propiedades
IA. M Contiene al entero 1, y,
IIA. Si M contiene al entero n, se puede demostrar que M contiene además al entero n+1, entonces M contiene a todos los enteros positivos.
La primera parte del axioma de inducción, IA suele llamarse base, y la segunda parte, IIA parte inductiva. El axioma de inducción es útil para demostrar ciertas expresiones matemáticas. Suponiendo que la proposición P(n) es verdadera o falsa dependiendo solo del valor de la n, el axioma de inducción se puede utilizar para demostrar que si
IB. P(1) es verdadera, y
IIB. El saber que P(n) es verdadera, implica que P(n+1) es también verdadera, entonces P(n) se cumple para cualquier n.

Usamos inducción sobre los naturales para: Demostrar que todos los números naturales tienen una cierta propiedad.
Ejemplo. 〖S(n)〗^ =∑_(k=0)^n▒〖k=(n(n+1))/2〗

Definir diversos objetos asociados a los números naturales: Definiciones inductivas/recursivas de funciones relaciones etc. Ejemplo: n!= 1, (n+1)!= (n+1)∗n!
La inducción nos permite demostrar que existe una única función: N→N que satisface las ecuaciones de arriba.
Hay al menos tres principios de inducción para los naturales que son equivalentes.




Principio simple de inducción (PSI)
Dado un subconjunto S de N (S⊆ N), si se cumple que
(I) 0∃ S;
(II) Dado cualquier n∃ N, si n∃ S entonces (n+1)∃ S; entonces S=N.
Principio de inducción por curso de valores
Dado un subconjunto S de N (S⊆ N), si se cumple que para todo nE N:
{kEN : k < n⊆ S⇒ S},(∗) entoces S=N. Aquí vemos que no hay una “base. Explicita”: solo hay un paso inductivo, y En este la HI es {kEN : k < n}⊆ S⇒ S y la TI es nE S. Principio del buen orden El principio del buen orden implica. El principio de inducción matemática Sea A un subconjunto de números naturales tal que, (1) Contiene al 1, y (2) Si contiene a n entonces contiene a n+1. Supongamos que A = N. Sea B=N-A el conjunto de números naturales que no están en A. Si A = N, entonces B= φ. Luego por el principio del buen orden, B tiene Un elemento más pequeño. Sean m∃ B el elemento más pequeño de B. Observar que m = 1 porque 1∃ A. Por lo tanto, m>1 y podemos escribir m= (m-1)+1, y m-1∃ N.
Observar que m-1 no existe B porque el número más pequeño en B es m.
Por lo tanto, m-1∃ A y entonces m= (m-1)+1∃ A.
Esto contradice la suposición”m es el elemento más pequeño de B.”
El principio de inducción matemática implica El Principio Del Buen Orden
Sea A un subconjunto de números naturales.
El principio del buen orden dice:
A = φ⇒∃m∈ A,∀n∈ A,m < n
Esto dice P⇒ Q, lo cual es equivalente a Q o∼ P. Es decir,
∃m∈ A,∀n∈ A,m < noA = φ
Supongamos que∼ Q. Es decir, que, ∀m∈ A,∃n∈ A,m≥ n
Sea B el subconjunto de N tal que 1, 2,3,...,k, no pertenecen a A.
Observar que 1∈ B.
(Porque 1∈ A⇒∀n∈ A,1 < n).
Por el principio de inducción matemática, B=N.
Por lo tanto A=vacio. Es decir, P

P Q PYQ
V V V
V F F
F V F
F F F

P Q POQ
V V V
V F V
F V V
F F F


P Q P Q
V V V
V F F
F V V
F F V

Como dijimos al principio, todos estos principios son equivalentes: cada una se puede demostrar a partir de cualquiera de los otros. A veces uno es más apropiado que otro, según el problema donde requiera aplicar.

Demostraciones mediante inducción

Demostraciones mediante inducción
1.- Usa el método de inducción para demostrar que la suma de los n primeros enteros positivos impares es n2
Solución: Sea P(n) la preposición que afirma que la suma de los n primeros enteros positivos impares es n2. En primer lugar debemos completar el caso base: debemos verificar que P(1) es verdadero. Luego llevamos a cabo el paso de inducción esto es debemos demostrar que p (k+1) es verdadera cuando se supone que P(k) es verdadera.
Paso base: P(1) afirma que la suma del primer entero es impar es 12. Esto es cierto puesto que el primer entero impar es 1.
Paso de inducción
Para a completar el paso de inducción debemos demostrar que la preposición
P(k) = p(k+1) es verdadera para todo entero positivo k esto es:
1+3+5+….+.. (2k-1) = k2.
Observa que k decimo entero positivo impar es (2k-1) ya que esta entero se obtiene sumando 2 en un total. Se tiene en cuenta que p(k+1) es verdadera suponiendo que p(k) es verdadera que p(k+1) es la sentencia que afirma que 1+3+5+…+(2k-1)+(2k-1) = (k+1)2
Por lo tanto suponiendo que p(K) es verdadera se sigue que
1+3+5+…+(2k-1)+(2k+1) = [1+3…+(2k-1)]+(2k-+1)
= k2 + (2k+1)
= k2 + 2k+1
= (k+1)2
Esto demuestra que P(K) = p(k+1). Se observa que se ha usado la hipótesis de inducción P(k) en la segunda igualdad para reemplazar la suma de los primeros k enteros por k2.
Puesto que p(1) es verdad y que p(K) = p(k+1) también lo es para todo entero positivo k el principio de inducción matemática muestra que P(n) es verdadera para todo entero positivo n.
2.- Usa el método de inducción para demostrar la desigualdad de n < 2n
Para todo entero positivo n.
Solución: sea P(n) la proposición n < 2n
Paso base: P(1) es verdadera puesto que 1<21 = 2
Paso de inducción: suponiendo que P(K) es verdadera para el entero positivo k. esto es suponemos que k < 2k. Necesitamos demostrar que P(K+1) es verdadera. Tenemos que ver que k + 1 < 2k+1. Sumando 1 en ambos lados de la desigualdad k<2k y teniendo en cuenta que 1 ≤ 2k tenemos
K+1 < 2k+1 ≤ 2k+2k = 2k+1
Hemos demostrado que P(k+1) es verdadera es decir que k + 1<2k+1 besándonos en la suposición de que P(K) es verdadera.
Se ha completado el paso de inducción matemática se ha demostrado que n < 2n para todo n positivo.
3.- Utiliza la inducción matemática para demostrar que 2n < n! para todo entero positivos n mayor o igual que 4.
Solución: sea P(n) la preposición que a firma que 2n < n!
Paso base: para demostrar la desigualdad para n ≥ 4 se requiere que el paso base sea P(4). Observa que p(4) es verdadera puesto que 24 = 16 <4! = 24
Paso de inducción: supongamos que P(k) es verdadera. Esto es que 2k < k! debemos demostrar que P(K+1) es verdadera esto es tenemos que demostrar que 2k+1 < (K+1)! Multiplicando ambos lados de la desigualdad 2k < k tenemos que
2.2k < 2.k!
< (k+1).k!
= (k+1)!
Esto demuestra que P(K+1) es verdadera cuando P(K) es verdadera lo que completa el paso de inducción de la demostración. Por lo tanto se ha demostrado que 2n < n! es verdadera para todo entero n n ≥ 4.

4.- Utiliza el método de inducción para demostrar que n3 - n es divisible entre 3 siempre que n sea un entero positivo.
Solución: para construir la demostración definamos P(n) como la sentencia n3-n sea entero positivo.
Paso base: P(1) es verdadera puesto que 13 + 1 = 0 es divisible entre 3
Paso de inducción: supongamos que P(k) es verdadera esto es que k3 – k es divisible por 3. Debemos mostrar que P(k+1) es verdadera esto es tenemos que demostrar que (k+1)3 – (k+1) es divisible por 3.
(k+1)3 – (k+1) = (k3 + 3k2 + 3k +1) – (k+1)
= (k3-k) + 3(k2+k)
Como los términos de esta suma son divisibles entre 3 (el primero por la suposición del paso de inducción y el segundo por que es tres veces un entero) se sigue que (k+1)3 + (k+1) también es divisible por 3. Esto completa el paso de inducción matemática por lo tanto n3 – n es divisible por 3 para todo n entero positivo.
5.- El número de subconjunto de un conjunto finito. Demuestra por inducción que si S es un subconjunto finito con n elementos entonces S tiene 2n subconjuntos.
Solución: sea P(n) la preposición que afirma que un conjunto con n elementos tiene 2n subconjuntos.
Paso base: P(0) es verdadera puesto que un conjunto con cero elementos el conjunto vacio tiene exactamente 20 = 1 subconjuntos; el único subconjunto que tiene es el mismo.
Paso de inducción: supongamos que P(k) es verdadera por lo que todo conjunto tiene 2k subconjuntos. Se deben demostrar que bajo esta suposición P(k+1) la sentencia que afirma que todo conjunto de k+1 elementos tiene 2k+1 subconjuntos debe ser también verdadera.

5.2.- RECURSIVIDAD
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 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, ….