Recursividad

he estado leyendo el libro de ‘Java Script: The Good Parts’ , y me tome con una técnica interesante …

Por esta ocasión vamos a poner un pequeño ejemplo, después trataré de explicarlo, al menos lo que yo entendí.

Código [JavaScript]:

//resolver la torre de hanoi :]
var hanoi = function hanoi(disco, origen, auxiliar, destino){
     if(disco > 0){
          hanoi(disco - 1 , origen, destino, auxiliar);
          document.writeln('Mover disco '+ disco + ' de ' + origen + ' a ' + destino + '<br />');
          hanoi(disco - 1, auxiliar, origen, destino);
     }
};
hanoi(4, 'Origen', 'Auxiliar', 'Destino');

Bien al ejecutar la función en este caso con discos = 4, nos mostraría los 15 movimientos para poder resolver la torre. Ahora que ya vimos la magia vayamos a explicar.

Una función recursiva, es una función que se llama a si misma, ya sea directa o indirectamente. La recursividad es una poderosa técnica de programación en el que un problema se divide en un conjunto de subproblema similares, cada uno resuelto con una solución trivial. En general, una función recursiva se llama a sí misma para resolver sus subproblemas.

Y el riesgo apa? .. Bueno pues en realidad todo se reduce al uso de memoria, ya que lo que esta haciendo es crear n numero de ‘referencias’ a si misma, y en que se traduce esto en reservar memoria por cada referencia, haciendo algunos ejemplos según yo no es infinita en algún momento hay un buffer overflow, así que habrá que tener mucho cuidado al momento de usar este jutsu XD

Dudas, criticas y correcciones en buen pedo! al los comentarios.. en mal pedo pos también xD
Anuncios

Demostrando raíz de 2 es irracional

– Demostración por Descenso Infinito –

La demostración comienza suponiendo que raíz de 2 no es irracional.

Podemos suponer que p y q son positivos. Nos interesa en sí que q > 0.

A partir de aquí demostraremos que raíz de 2 es igual a otra fracción cuyo denominador también es positivo y además menor que q. Esto implicaría que podríamos encontrar una sucesión de números enteros positivos decreciente infinitamente, lo cual es imposible.

Ahora veamos que la fracción cuyo numerador es 2q – p y cuyo denominador es p – q también es igual a raíz de 2.

Veamos ahora que 0 < p – q < q:

En el penúltimo paso hemos multiplicado por q la cadena de desigualdades y en el último hemos restado q. Por tanto hemos encontrado otro entero positivo menor que q que cumple que es el denominador de una fracción que es igual a raíz de 2. Con esta nueva fracción podríamos hacer lo mismo y encontraríamos otro entero positivo menor que p – q que cumpliría lo mismo. Es decir, podemos encontrar una sucesión infinita y decreciente de enteros positivos cumpliendo lo anterior.

Y como ya sabremos eso no es posible, ya que no existe ninguna sucesión de enteros positivos decreciente con infinitos términos.

 
Fuentes:
Math Fun Facts
Google