03.08.2012 15:21

 

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, este método de demostración  suele ser muy útil en problemas en los que se trata de probar que todos los números naturales (1, 2, 3...) cumplen una cierta propiedad: consta de dos pasos:

·         Primero, se demuestra que el 1 cumple la propiedad.

·         A continuación, se supone que la propiedad es verdadera para un cierto número n (arbitrario) y se demuestra para el número siguiente, el n+1.

Si se consigue, esto demuestra la propiedad que queríamos para todos los números naturales, de forma parecida a las filas de fichas de dominó cuando caen: hemos demostrado que la primera ficha (el 1) cae (primer paso), y que si cae una ficha también debe caer la siguiente (si es cierta para n, debe serlo para n+1, segundo paso). La idea de la inducción es muy clara: si un número cumple algo, y si cuando un número lo cumple el siguiente tiene que cumplirlo, entonces todos los números lo cumplen.

Premisa mayor: El número entero   tiene la propiedad .

Premisa menor: El hecho de que cualquier número entero   tenga la propiedad P implica que n + 1 también la tiene (que se anota n→ n+1).

Conclusión: Todos los números enteros a partir de a tienen la propiedad

.

DEMOSTRACIONES POR INDUCCIÓN

 

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

§  Se demuestra que P⁰ el primer valor que cumple la proposición (iniciación de la inducción), es cierta.

§  Se demuestra que si se asume Pⁿ cierta y como hipótesis inductiva, entonces Pⁿ⁺¹ lo es también, y esto sin condición sobre el entero natural ⁿ (relación de inducción).

La inducción puede empezar por otro término que P ⁰, digamos por  ^no. Entonces Pⁿ será válido a partir del número n⁰, es decir, para todo natural 

 

EJEMPLO 1

 

Para todo  n ≥ 1 ,6ⁿ un número que acaba en 6.

Sea Pⁿ la proposición: « 6 ⁿ en 6».

§  Es claro que  P ¹ es cierto, porque 6 ¹ = 6.

 

RECURSIVIDAD

Se aplica a sistemas dentro de sistemas mayores y a ciertas características particulares, más bien funciones o conductas propias de cada sistema, que los semejantes a la de los sistemas mayores y éste puede aplicarse a los diferentes campos del conocimiento como lo son: Administración, Recursos Humanos, Sistemas de Información, etc.

Principio de Recursividad: Lo que este principio argumenta es que cualesquier actividad que es aplicable al sistema. Las funciones resuelven cometidos concretos y llevan parámetros que las hacen ser útiles para distintas situaciones. Las funciones que hemos visto hasta ahora se resolvían por sí mismas o, a lo sumo podían pedir ayuda otras funciones que terminaban resolviéndose sin más llamadas. Sin embargo, hay veces en que una función solo se puede resolver volviéndose a llamar a si mismas. Se trata de funciones recursivas.

 

DENTRO DE LA TEORÍA DE LA RECURSIÓN, SE TIENE QUE EXISTEN DIFERENTES TIPOS DE RECURSIÓN:

 Recursión directa. Cuando el código F tiene una sentencia que involucra a F. 

 Recursión indirecta o cruzada.- Cuando la función F involucra una función G que invoca a la vez

 una función H, y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de Par o impar. 

 Recursión simple.- Aquella en cuya función solo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos interactivos. 

 Recursión múltiple.- Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de transformar a interactiva. Por ejemplo el algoritmo de Fibonacci. 

 Recursión anidada.- En algunos de los argumentos de la llamada hay una nueva llamada a sí misma. 

 Recursión infinita. La iteración y la recursión pueden producirse infinitamente. Un bucle infinito ocurre si la prueba o test de continuación del bucle nunca se vuelve falsa. 

En realidad, la recursión infinita significa que cada llamada recursiva produce otra llamada recursiva y esta a su vez otra llamada recursiva, y así para siempre. En la práctica, dicha función se ejecutará hasta que la computadora agote la memoria disponible y se produzca una terminación anormal del programa. 

EJEMPLO:

 

Implementar un método recursivo que imprima en forma descendente de 5 a 1 de uno en uno.

 

Programa:

Public class Recursividad {

    void imprimir(int x) {

        if (x>0) {

            System.out.println(x);

            imprimir(x-1);

        }    

    }

    public static void main(String[] ar) {

        Recursividad re=new Recursividad ();

        Reimprimir (5);

  }