UNIDAD V

05.08.2012 16:29

RECURSIVIDAD

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 circuito sin fin en esta definición:

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 induccion sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Para que se entienda mejor a continuación se exponen algunos ejemplos:

  • Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar introduccion por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.
  • Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por induccion podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)..

Nota: aunque los términos "recursión" y "recursividad" son ampliamente empleados en el campo de la informática, el término correcto en castellano es recurrencia. Sin embargo este último término es algo más específico. Véaserelacion de recurrencia.

Un ejemplo de conjunto definido de forma recurrente es el de losnumeros naturales:

a) 0 pertenece a N
b) Si n pertenece a N, entonces n+1 pertenece a N
c) Si X verifica a) y b) , entonces X está incluido en N

Los números naturales es el conjunto de números enteros no negativos.

 

 

INDUCCION MATEMATICA.

 

de un parámetro n\, 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 a\, tiene la propiedad P\,.
Premisa menor: El hecho de que cualquier número entero n\, tenga la propiedad P\, implica que n+1\, también la tiene (que se anota n \Rightarrow n + 1).
Conclusión: Todos los números enteros a partir de a\, tienen la propiedad P\,.
 

El razonamiento para demostrar una proposición cualquiera mediante el esquema del razonamiento es como sigue. Llamemos P_n\, a la proposición, donde n\, es el rango.

  • Se demuestra que P_0\,, el primer valor que cumple la proposición (iniciación de la inducción), es cierta.
  • Se demuestra que si se asume P_n\, como cierta y como hipótesis inductiva, entonces P_{n+1}\, lo es también, y esto sin condición sobre el entero natural n\, (relación de inducción).

Luego, demostrado esto, concluimos por inducción, que P_n\, es cierto para todo natural n\,.

La inducción puede empezar por otro término que P_0\,, digamos por P\,n_o\,. Entonces P_n\, será válido a partir del número n_0\,, es decir, para todo natural n \ge n_0\,.

Ejemplo 1

Para todo n \ge 1, 6^n\, es un número que acaba en 6.

Sea P_n\, la proposición: «6^n\, acaba en 6».
  • Es claro que P_1\, es cierto, porque 6^1 = 6\,.
  • Supongamos que P_n\, es cierto para un valor de n\, natural, y probemos P_{n+1}\,.
Un entero acaba por 6 si se puede escribir así: 10a+6\,, con a\, entero positivo o igual a cero. La hipótesis es, pues, 6^n=10a+6\,.
Entonces 6^{n+1}=6(10a+6)=60a+36=60a+30+6=10(6a+3)+6=10c+6\,, con c=6a+3\,, entero.
Esta última escritura prueba que 6^{n+1}\, acaba por 6, o sea que P_{n+1}\, es cierto.
Luego P_n\, es cierto para todo n \ge 1\,.

La inducción es válida por la construcción misma del conjunto de los naturales mediante los acciomas de peano. En este caso:

  • 1 es un natural;
  • si n\, lo es, entonces n+1\, (sucesor de n\,) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la induccion transfinita, y la inducción sobre las fórmulas de la logica propocicional.

Además de la demostracion por induccion, existe la definición o construcción por inducción. Por ejemplo, una sucesión aritmética puede ser definida como función de n\,: u_n = a + rn\,, o por inducción:

  • u_0 = a\,
  • u_{n+1} = u_n + r\,.

Ejemplo 2

Véase también:sumatorio.
Se tratara de demostrar por inducción la siguiente proposición:
\sum_{k=1}^n (2k - 1) 3^k = (n - 1) 3^{n+1} + 3 \forall n \in \mathbb{N}
1. Se comprueba para n=1
\sum_{k=1}^1 (2 - 1) 3^1 = 3 = (1 - 1) 3^{1+1} + 3
Se tiene por tanto que la proposición es verdadera para n=1
2. Hipótesis inductiva (n=h)
\sum_{k=1}^h (2k - 1) 3^k = (h - 1) 3^{h+1} + 3
3. Tesis inductiva (n=h+1)
\sum_{k=1}^{h+1} (2k - 1) 3^k = (h + 1 - 1) 3^{h+1+1} + 3
\sum_{k=1}^{h+1} (2k - 1) 3^k = h 3^{h+2} + 3
4. Demostración de la tesis con base en la hipótesis
\sum_{k=1}^{h+1} (2k - 1) 3^k = \sum_{k=1}^{h} (2k - 1) 3^k +(2(h+1) - 1) 3^{h+1}
Se aplica la hipótesis de inducción:
\sum_{k=1}^{h+1} (2k - 1) 3^k = (h - 1) 3^{h+1} + 3 + [2(h+1) - 1] 3^{h+1}
\sum_{k=1}^{h+1} (2k - 1) 3^k = (h - 1) 3^{h+1} + 3 + (2h+2 - 1) 3^{h+1}
\sum_{k=1}^{h+1} (2k - 1) 3^k = 3^{h+1} (h - 1 + 2h + 1) + 3 (sacando factor común)
\sum_{k=1}^{h+1} (2k - 1) 3^k = 3^{h+1} 3h + 3
\sum_{k=1}^{h+1} (2k - 1) 3^k = h 3^{h+2} + 3
Por lo tanto, por verificarse la proposición para n=1 y para n=k+1 siendo k cualquier número natural, la proposición se verifica \forall n \in \mathbb {N}
Volver