Seguidores

martes, 1 de febrero de 2011

Recursividad

Por alguna razón, la recursividad y los métodos recursivos me resultaron interesantes desde el primer momento.  Fué un amor a primera vista.

Algo recursivo es algo que se define en términos de sí mismo.  Los métodos recursivos, en general parten de poca información conocida (los casos triviales de un problema) y mediante la "paciente" descomposición de un problema P en problemas más pequeños (Q), resuelven estos y montan la solución al problema grande.

La primera vez que recuerdo haber visto algo recursivo fue en la segunda o tercera película del planeta de los simios.  En la peli, mostraban una imagen con efecto Droste (era un niño, así que todavia no sabía como se llamaba este efecto) y me dejaron impactado.

El efecto Droste consiste en imágenes que se contienen a sí mismas una y otra vez.  La técnica también se conoce como "mise en abyme" (puesta en abismo).   El nombre viene de una empresa Holandesa que comercializaba cacao en polvo y tenía una imagen con este efecto, que os pongo (tomada de Wikipedia)

Años después, cuando se pusieron "de moda" los fractales, descubrí un montón de imágenes que se generaban de forma recursiva.  Os pongo la carpeta de Sierpinsky (tomada de Wikipedia).

Posteriormente me encontré con la recursividad en empresariales en unas cuantas asignaturas.  Recuerdo que en alguna asignatura hablaban de los fenómenos de autocorrelación y la definían como "cuando la ley que explica un fenómeno está contenida en el mismo".    Es una definición poco formal y casi poética.

Más tarde me la volví a encontrar, esta vez "en todo su esplendor" en ingeniería informática.   La recursividad se puede aplicar a gran número de problemas que se resuelven mediante el uso de ordenadores.  No quiero abundar en esta parte, ya que pretendo una aproximación "amable" al tema.

En la naturaleza, la recursión es algo muy frecuente, la vemos en los brócolis, en los helechos, en el sistema circulatorio, respiratorio, etc.  Otra cualidad que se aprecia es la autosimilaridad, donde las partes son similares al todo, variando únicamente en el factor de escala.

En fin, por hoy esto es todo.   Hale, un par de imagenes más.

12 comentarios:

  1. Ejemplos típicos de funciones recursivas pueden ser el cálculo del factorial de un número, el método de ordenación quick-sort, etc. Vamos a distinguir un método iterativo frente a un método recursivo con el ejemplo del cálculo del factorial de un número n.

    FACTORIAL DE N: n!=n·(n-1)·(n-2)...2·1

    Método iterativo para calcular el factorial de un número n dado:

    int factorial(int n){

    int resultado=1;
    for(int i=1; i<=n; i++){
    resultado = resultado * i;
    }
    return resultado;
    }


    Método recursivo que realiza lo mismo que el código anterior pero de forma recursiva:

    int factorial(int n){

    if(n==0){
    return 1;
    }
    return (n*factorial(n-1));
    }

    Ahora si que está claro el post Pepe.
    Es siempre mejor ilustrar con ejemplos para todos los públicos...jeje.

    Salu2

    ResponderEliminar
  2. Lo que aprende una leyendo blogs y luego dicen que no sirven para nada...
    Gracias Pepe por la información. (Y a Toni también)
    Tengo la sensación de salir de clase ahora y miedo me da el día que me pongan el examen.

    Un beso

    ResponderEliminar
  3. Qué interesante Pepe. Me encantan tus entradas. Siempre aprendo algo. Graaaaacias

    ResponderEliminar
  4. La nieve también sería recursiva?????

    ResponderEliminar
  5. Vosotras sí que sois recursivas. En fin, amores a primera vista.

    ResponderEliminar
  6. Madre mía, Pitt. ¡Qué complejo! Yo entendía por recursivo aquello que puede repetirse una y otra vez. Pero gracias por ampliar el pobre concepto que tenía acerca de ese término.

    Besossss.

    ResponderEliminar
  7. Quiero dejar un comentario, pero al blog, no a este post:
    Yo te vi nacer... sólo y asustado... ahora eres grande y fuerte, lleno de amigos... ¿por qué? ¿una mezcla justa de sinceridad, cultura y humor? (y las cosas de Pepe)y la gracia de Pitt...
    Siempre que me paseo por aquí... me río... ¿y vosotros?

    ResponderEliminar
  8. Toni: estás fuerte en este tema. Gracias por tu aportación. Una vez tuve una sorpresa con Quicksort por usar un algoritmo recursivo muchas veces con un lenguaje que no soportaba bien la recursión. La primera ejecución de quicksort era perfecta y en alguna de las sucesivas, petaba. El problema es que se llenaba la pila. Es decir, hay que usar un lenguaje que soporte bien la recursión o que al menos te permita decidir cuando vas a compilar el tamaño de pila que vas a utilizar, para que no pete.

    ResponderEliminar
  9. Anne: Tranquila por el examen. Aprobado general y ya está.

    Yolanda Quiralte: Gracias a tí, por seguirnos todo este tiempo y enriquecer este blog con tu presencia y tus comentarios.

    ResponderEliminar
  10. marikosan: Los cristales de nieve adoptan patrones fractales muy variados. Por cierto son preciosos. Hay una forma fractal, llamada copo de nieve de Koch, que es parecida a algunos de los cristales de nieve.

    ResponderEliminar
  11. Aniki: No, lo que se repite una y otra vez es por ejemplo, mi padre, que me recuerda n veces la misma cosa. Lo recursivo, en general, es menos plomo que las personas.

    kassandra: Gracias por tu amable comentario. Pitt y yo también te tenemos en alta estima. Muchas veces si que me río. Sobre todo con algunos post del cachondo de Pitt.

    ResponderEliminar
  12. A mi también me gustan los recursivos! y eso que alguna vez me ha costado sacar alguna cosa que los utiliza. Que bien poder comprender algunas de las cosas que escribes Pepe!! :D

    ResponderEliminar