Para entender la recursividad primero hay que entender la recursividad
Si ya entendiste la recursividad no leas esto.
La recursividad funciona de la siguiente manera:
-
Primero se tiene una o más condiciones base. Estas condiciones son usadas para saber cuando hay que parar.
-
Se tienen varios parámetros de entrada con los que se va a trabajar. Uno o varios de estos parámetros serán usados en las condiciones base.
-
Finalmente se tienen varias operaciones a realizar. La funcion que estamos definiendo será resuelta al llamarse a sí misma con parámetros nuevos, de lo contrario entrará en un ciclo infinito
Entonces, con esta información en mente, podemos hacer el siguiente pseudo código para ver si existe un elemento usando busqueda binaria
Como se puede ver, cada vez que se parte la lista en dos, la lista se hace más chica, llegará al punto en que tenga un solo elemento o esté vacía. Cuando eso suceda, nuestras condiciones base pararán la recursión.
Ees mucho más fácil, si primero se identifican las condiciones base y luego se identifica como modificar los argumentos.
Es muy importante, primero intentar esto en pseudo-código o en lápiz y papel antes de intentar programarlo. Así lidiamos primero con la lógica y luego con el lenguaje de programación. Yo encuentro muy eficaz crear funciones auxiliares, que me ayuden a no atorarme cuando estoy pensando el el pseudo-codigo, es este caso las funciones auxiliares son: "primerElemento(), elementoDeEnMedio(), primeraMitad() y segundaMitad() ). Estas auxiliares no son relevante al problema, Cuando hay que implementarlo ya habrá dudas especificas, pero por lo pronto nos permiten que el pensamiento fluya.
Espero que esto ayude a entender mejor la recursividad.
Si aún no le has entendido, ve este link
- OscarRyz's blog
- Inicie sesión o regístrese para enviar comentarios
Sorprendente...
Me parece un excelente ejemplo, pero que utilidad se le puede dar en un problema real? o en que podria ocuparlo? un reporte? una busqueda?
Un reporte, una búsqueda, o
Exacto, un reporte, una búsqueda, o por ejemplo para ordenar elementos.
De hecho Java utiliza recursividad para su método de ordenamiento en Arrays.sort() que es utilizado por millones diariamente.
La recursividad es algo
La recursividad es algo tremendo y mucho más rápida que utilizar ciclos. Francamente lo puedes usar en labores tan ridículas (cómo la típica tareaita de imprimir un arreglo) así cómo ya en cosas mucho más pro (ordenamientos).
Es algo maravilloso, hay un dicho:
"To iterate is human, to recurse is divine"
velocidad
Recursión es más rápida que iteración? Cuidado con esos absolutos... yo creo que depende de la implementación de tu ciclo, y del lenguaje/plataforma/arquitectura de hardware, porque aunque el principio de recursión es el mismo en cualquier plataforma, no se implementa igual en todos los lenguajes y plataformas, y por lo tanto no va a tener el mismo performance una invocación recursiva en Java que en Ruby que en PHP que en C que en C++ que en Groovy que en .NET.
Además, el uso de recursos es muy distinto. No es lo mismo recorrer los elementos de un arreglo en un ciclo iterativo, que hacerlo de manera recursiva, en donde te puedes acabar la memoria si el arreglo es muy grande porque cada llamada recursiva incrementa el uso del stack.
En términos generales la
En términos generales la recursividad es más lenta que los loops; es por eso que en algunos lenguajes se puede optimizar la recursión de cola ( tail recursion que es aquella donde la llamada ocurre al final de la función) precisamente con un loop.
De una forma similar, algunos loops pueden ser optimizados con un GOTO e incluso eliminados.
Lo interesante es precisamente que un algoritmo recursivo es más sencillo de explicar ( por que se explica a así mismo ) que su contraparte iterativa y si eventualmente se vuelve un cuello de botella, siempre puede cambiarse, solo que hay que mantener el estado de ejecución a mano.
Otro ejemplo
Otro ejemplo, puede ser,.... busqueda sencilla:
Re: velocidad
Igual también en loops con arreglos grandes también hay casos en donde adios RAM (recuerdos de estructuras de datos...en donde podía recorrer arreglos de 10millones de elementos con recursividad, pero no con ciclos). También siempre que probabamos búsquedas en listas era más rápida la recursividad que los ciclos. Por eso se me quedó la idea =)...de no ser así una disculpa.
ejemplos
En general, cualquier algoritmo que se pueda implementar con recursión se puede implementar también de manera iterativa. La decisión entre uno y otro se puede basar en criterios como desempeño y lo entendible que quede el código. Y repito, según la plataforma puede ser más rápido usar ciclos o recursión, pero con recursión siempre vas a tener la limitante del stack.
Dos ejemplos de mundo real: vean la segunda y quinta imágenes.
Re: ejemplo
Si tienes razón he probado con Ruby y Python. En python es más rápida la recursividad en arreglos pequeños, pero en arreglos grandes de más de 3millones truena...En Ruby es más rápido el bien ponderado:
Si a esto el agregamos que en Ruby al elemento 8700 (más o menos) se quejaba del stack cómo tu dices. =)
**OFF TOPIC-ON RESPONSE:Jajaja...Mac-ero y anti-ms.[sarcasm] ¿Porqué el odio contra MS?, es algo que aun no entiendo. [/sarcasm]
Hice esa pregunta
Hice esa pregunta precisamente aquí
En resumen:
Todas las soluciones recursivas pueden ser escritas en forma no recursiva. Lo que se necesita es mantener es estado en una pila local donde se saque y ponga el elemento en turno.
Obvio, la implementación puede ser un horror. Lo que se gana con recursividad es simplicidad
arreglo.each
Pero arreglo.each do |a| blabla end en Ruby es iterativo, no recursivo. Se ejecuta el código "blabla" con cada elemento de la lista; finalmente es la estructura básica de ciclos, que se puede hacer con un for por ejemplo en cualquier otro lenguaje, donde tomas un elemento de una lista y ejecutas cierto código con ese elemento.
Pues yo nunca he encontrado
Pues yo nunca he encontrado como recorrer todos los elemento de una lista tipo arbol utilizando ciclos, solo recursividad, si alguien tiene algun ejemplo de como hacerlo con un for o un while, bienvenido.
Ahhh no me retes, que tengo
Ahhh no me retes, que tengo muchas flojera... :) Si si alguién lo hace que lo postee.. A ver preguntemosle a google
A méndigo Google, sabe todo:
A méndigo Google, sabe todo: Este es el primer hit ( no sé si esté correcto, además es en Sicharp )
Re: arreglo.each.
Por eso, dije que era más rápido que la recursividad a eso me refería.
Re: A méndigo Google, sabe todo:
mmm...al parecer funciona pero sólo para árboles no balanceados (o eso es lo que me da a entender el código).
EDIT: Haciendo una revisada parece que me tendré que tragar mis palabras, si funciona para árboles balanceados también (no había visto el último else).
recursión vs iteración
Nopalin, no digo que sea malo hacer algoritmos que utilicen recursión o que solamente se deba utilizar iteración o que uno sea mejor que otro. Simplemente dije que cualquier algoritmo que se implemente usando recursión, también se puede hacer con iteración. No significa que siempre uno sea mejor que otro. Ciertos problemas se resuelven mejor con recursión pero otros se resuelven mejor o son más robustos usando iteración. Lo de los árboles es un buen ejemplo porque la estructura misma se presta para recorrerla utilizando recursión; ya vimos que sí se puede hacer lo mismo con iteración, pero es más complicado. Cada uno tendrá sus ventajas y desventajas (menos código pero la limitante del stack trace vs. código más complicado y tal vez hasta menor desempeño pero puede recorrer árboles más grandes).
Buen post @OscarRyz
Obvio, la implementación puede ser un horror. Lo que se gana con recursividad es simplicidad
Yo de plano he tenido un poco de problemas al entenderle a la recursividad.
Por lo poco que he entendido hay dos tipos (o formas) de crear funciones o procedimientos recursivos:
yo del factorial y del código de Hanoi no paso ja ja ja.
En general, cualquier algoritmo que se pueda implementar con recursión se puede implementar también de manera iterativa. La decisión entre uno y otro se puede basar en criterios como desempeño y lo entendible que quede el código. Y repito, según la plataforma puede ser más rápido usar ciclos o recursión, pero con recursión siempre vas a tener la limitante del stack.
@ezamudio, me recuerdas a un profe de programación en paralelo que decia exactamente (bueno casi) lo mismo.
Groovy
Pues en la sesión de hoy del curso de Groovy, a MrDajarck se le ocurrió el ejercicio de leer un archivo con una lista de números y sacar su factorial.
Usando recursividad me quedó así:
Con números del 1 al 10 la salida fue:
más ejemplos
Para mí, la mejor manera de calcular un factorial es iterativa. Ejemplos en Groovy y Scala para sacar 10!:
Eso es básicamente un "fold left" en programación funcional. En Scala hay 2 maneras de invocar el foldLeft, y además hay una manera más fácil de calcular el factorial:
Ahora, en cuanto a recursividad... hace poco necesitaba implementar una función para convertir una cadena separada por espacios, en una lista. En Groovy por ejemplo puedo simplemente hacer
Lo que no me gusta de la versión recursiva es que estoy manejando una lista mutable. En Scala es más fácil manejar listas inmutables, por lo que la versión recursiva es más fácil de implementar, y además se puede implementar de modo que se utilice la optimización de tail recursion que mencionó Oscar:
Pero esta implementación es engañosa; es puramente recursiva. Parece que el compilador podría aplicar la optimización de tail recursion que mencionaba Oscar, pero no es así, porque la última llamada en la función no es a
Esto es muy útil porque efectivamente hay algoritmos que se expresan mejor de manera recursiva, y pues el compilador nos puede ayudar a que se ejecuten de manera iterativa.