Credit image

¿Te gusta el diseño web? ¡Echa un vistazo a la documentación de LenguajeCSS.com!

Recursividad: Entender lo entendible

Hace una semana, en la asignatura de Metodología de la Programación I hemos empezado a dar un tema que me interesaba bastante dentro del temario de la programación básica, que es la recursividad.

La recursividad tiene una curiosa definición, que intentaré explicar sin meterme en detalles técnicos: Se trata de realizar una función, de modo que antes de terminarla la has vuelto a comenzar a realizar.

Para comprender esta enrevesada definición se me ocurre un ejemplo sencillo: Nos encontramos en un gran apartamento y estamos buscando a una persona. Para encontrarla realizamos una acción (abrir la puerta de una habitación) para comprobar si está dentro esa persona. Ocurre que dentro de esa misma habitación pueden haber varias habitaciones más (baño y cocina por ejemplo) y a su vez, dentro de la cocina un trastero. Así pues, una vez entrado en la primera habitación mencionada y no encontrar a la persona que buscamos, nos meteremos en la cocina y si no está, buscaremos en el trastero.

Aprovechando ya este ejemplo desarrollado, en el caso de que tampoco encontraramos a la persona en el trastero, deberíamos retroceder hasta encontrar una habitación anterior que posea una habitación -valga la «rebuznancia»- en la que aún no hayamos mirado, y así sucesivamente. A esto último se le denomina Backtracking (Volver atrás).

Investigando un poco más sobre el tema, doy con algunos de los ejercicios propuestos en años anteriores en mi facultad como el juego de Las torres de Hanoi -donde se entiende muy bien el uso de la recursividad en ámbitos de programación-, la función de Ackermann o la sucesión o serie de Fibonacci.

Además de todos estos ejemplos, existe uno que me llamó mucho la atención. Se trata del número de oro (Φ), que se mantiene presente -por ejemplo- en la forma en la que se crean las caracolas o los árboles y que era considerada una cifra con multitud de propiedades mágicas por los antiguos filosofos griegos:

Este año nos ha tocado hacer un asistente para resolver sudokus, juego numérico que se ha puesto muy de moda últimamente, y práctica que me ha resultado bastante interesante. En cuánto pase la semana de entrega de la práctica subiré el código, si a alguien le interesa.

EDITADO: En este artículo explicativo del backtracking (volviéndo atrás) podrás encontrar el Asistente para resolver sudokus en Pascal.

Escrito por Manz, el , en programacion. Comentarios recibidos: 30.

30 comentarios de lectores
NoAlWin
NoAlWin
1

Como se ve mejor con ejemplos (lamentablemente esto no me coge los tabulados asi que se lee peor)......... program Ejemplo(output); Procedure Recursiva(i:INTEGER); Begin (*Aumentamos el valor de i*) i:=i+1; (*Y lo escribimos*) write(i,' '); (*Si i vale menos de 5 nos llamamos a nosotros mismos *) if(i<5)then Begin Recursiva(i); End; (*Volvemos a escribir i*) write(i,' '); End; (* Programa Principal*) Begin (*Hacemos la primera llamada con 0*) Recursiva(0); (*Metemos un salto de linea*) writeln(); End. Lo que pasa es que * Ejemplo (el programa principal) llama a recursivo con el parametro 0. * Recursiva guarda el 0 en la variable i, aumenta su valor a 1 escribe su valor y si vale menos de 5 se llama a si misma con el valor 1. * Se crea una nueva Recursiva que guarda el 1 en i, aumenta su valor a 2 escribe su valor y si vale menos de 5 se llama a si misma con el valor 1. ----------------------------- * Se crea una nueva Recursiva a la que pasan el 4 y lo guarda en i, aumenta su valor a 5 escribe su valor, como no vale menos de 5 ssigue ejecutando. Vuelve a escribir i (5) y sale. * Volvemos a la Recursiva que llamo a la anterior y seguimos ejecutando donde nos quedamos osea que escrivimos en valor de i (4) y salimos. ----------------- * Volvemos a la primera recursiva que escribe su valor y sale. *Volvemos a ejemplo que escribe un salto de linea y sale de la ejecución. Y lo que hace es escribir 1 2 3 4 5 5 4 3 2 1

Ruyk
Ruyk
2

La recursividad, como concepto teórico para resolver problemas, es bastante práctica, pero no tenemos que olvidar que utilizar recursividad es MUY ineficiente!, Así que hay que evitarla en la medida de lo posible. Si no se puede encontrar un algoritmo no-recursivo alternativo, siempre se puede recurrir a simular la recursividad con una pila. Pasa como todo en la informática: es bonito, fácil, interesante... pero... es ineficiente! xD

Driadan
Driadan
3

La recursividad no está solo presente en la programacion, tambien en muchos otros aspectos de la vida y la gente hasta inventa acronimos recursivos: GNU ... Stack Overflow

Elaine Marley
Elaine Marley
4

Bueno, yo de recursividad ni papa, pero el numero de oro (o aureo) no solo se encuentra en la naturaleza, sino que el hombre lo aplicó a numerosas construcciones, desde el Partenon Grecia hasta nuestros dias, pasando por el Renacimiento. Al fin y al cabo algo tiene que ver la arquitectura con la programación, no? ;)

  • -1
balmasedano
balmasedano
5

Interesante definición de recursividad, Manz, ahora ya no hay excusa para no entender el concepto. Saludos.

  • -1
Manuls
Manuls
6

En mi experiencia personal, decir que la recursividad me costó bastante entenderla, pero una vez que "cambias el chip", te salen funciones recursivas muy fácilmente (al menos las que no tienen dificultad excesiva) Por ciero, quero el codigo :P

  • -1
Viktor
Viktor
7

La recursividad, una vez entendida, es una herramienta muy comoda de utilizar. Pero como dicen es ineficiente, asi que no me extrañaria que en clase tambien os enseñen (si no os lo han enseñado ya) como pasar de algoritmos recursivos a iterativos. Por aqui (Zaragoza) tambien hemos tenido que resolver sudokus por backtracking, en nuestro caso con ADA

  • -1
Tankian
Tankian
8

La definicion que mas me ha gustado de recursividad es la que deberia aparecer en los diccionarios: Recursividad: Vease "Recursividad" xD

  • -1
Marche Radiuju
Marche Radiuju
9

Sigo intentando entender el significado de Recursividad pero con el ejemplo de Manz aun me he liado más.¿Querria decir que si yo estoy creando una maqueta y voy por la mitad, la destruyo y comienzo de nuevo? ¿Eso, por ejemplo, seria recursividad?

NoAlWin
NoAlWin
10

¿Querria decir que si yo estoy creando una maqueta y voy por la mitad, la destruyo y comienzo de nuevo? ¿Eso, por ejemplo, seria recursividad? No, más bien sería hacer una maqueta dentro de una maqueta. O más sencillo, crear robots que creen robots que creen robots que creen robots que creen robots.......... La recursividad se basa en ir simplificando el problema en cada llamada a la función recursiva hasta llegar a un caso trivial de resolver. Una vez ahi la solución va recorriendo el camino inverso, es decir, va siendo devuelta a la función padre, esta a su vez puede tratar esta solución.

DaNiTo
DaNiTo
11

Un ejemplo aún más claro, me gustó el ejemplo de NoAlWin :) Imaginemos que tenemos una carpeta para nuestras descargas y que a su vez tenemos en la carpeta principal otras con un título diferente según su contenido, una puede ser llamadas películas, otra música y otra fotos. En películas podemos crear otra serie de carpetas según los tipos de películas, terror, ciencia-ficción, acción.. Y a su vez en cada una de ellas ordenadas por director o actor/actriz principal. De vuelta a la carpeta principal vamos a música y allí tenemos hip-hop, rock... Y a su vez en una carpeta van ordenadas por artistas y luego en artistas va cada uno de sus discos... |-/home |-- /Películas |--- /Acción |---- /Arnold Schwarzenegger |----- /Terminator |------ /... |---- /Jet Li |----- /... |--- /Terror |---- /Pesadilla en Elm Street |----- /... |---- /Saga Scream |----- /Scream 1 |----- /... |-- /Música |--- /Hip-Hop |---- /Nach |----- /... |---- /Doble V |----- /... |--- /R&B |---- /... |----- /... |-- /Fotos |--- /Fiestas |---- /Fin de año 199x |---- /( " ) 200x |--- /Cumpleaños |----- /... |--- /Amig@s |---- /Fulano1 |----- /Fulano1 en ... |---- /... |----- /... Tal vez se complica un tanto la cosa al verla así, pero, el caso es que tendremos que volver siempre nuestros pasos para encontrar la ruta inicial o en este caso la carpeta anterior, que es más o menos lo que quería decir Manz con el ejemplo de encontrar a una persona en un apartamento. ¿Al final la encontraste?

Johnymepeino
Johnymepeino
12

Creo que a veces es bueno no tener ni papa porque lo captas (extraño en mí) al instante. Otra cosa es (faltaría plus) saber hacerlo pero para eso ya estais vosotros ^^ En serio: gracias a este blog, y a su dueño porque además de entretido siempre resulta didáctico.

Prozac
Prozac
13

Wow si que se han liado con lo de la recursividad XDXD jaja pues el ejemplo clasico es el de fibonacci, de backtracking estan las 8 reinas, la vuelta del caballo, o las torres de hanoi, tambien es bueno decir que todo problema iterativo tiene una "alternativa" recursiva. Imaginen imprimir del 0 al 4 iterativo for(i=0;i<5;i++){ imprimir(i); } recursivo seria int recursivo(int n){ if(n==5) return 0; else{ imprimir(n) recursivo(n+1); } } recursivo(0); y si no me equivoque XDXD ambos imprimiran del 0 al 4, en este caso no se nota mucho la utilidad pero normalmente un algoritmo recursivo es mucho mas corto y "elegante" que uno iterativo PD: imaginen que imprimir imprime en pantalla XD

Viktor
Viktor
14

Otro ejemplo seria el de calculo de un numero factorial: n! = n * (n-1) * ... * 2 * 1 function factorial (n: integer) return integer is begin if n=0 then return 1; else return n*factorial(n-1); end if; end factorial;

interesado
interesado
15

y donde se encuentra la misteriosa práctica del señor Manz que dijo que la subiría ? No la encuentro, gracias.

Kong
Kong
16

Manz ya comentó que subiría la práctica en cuanto pasarán las semanas de corrección de prácticas porque sino la gente se puede copiar y sancionarle. Seguramente desde que pase la semana de examenes subirá la práctica.

interesado
interesado
17

a día 12 de febrero aun no ha dado señales de que publicará la práctica, o quizás soy tan tonto que no la encuentro...

PEpote
PEpote
18

eee olaa y la practica esa que iban a subir cuando ava a seeeéééé!!!!! la necesito y hace muuuuuuuuchoooo que pusieron estoooo porfavurrr mademnela aaa elpiojito_17@hotmail.com besos

rickymax01
rickymax01
19

que tal con la recursividad la verdad prefiero lo iterativo pero vaya que me toca aprenderla y seguir

Chk
Chk
20

El ejemplo de la casa me parece interesante, pero yo diría que la primera vez estás en la calle, abres la puerta y entras a la casa, observas que tiene dos floreros, tres cuadros y una puerta muy misteriosa de color ébano. Abres la puerta, entras y adivina que?..haz vuelto a entrar a tu casa, con las mismos flores, cuadros e incluso la misma puerta misteriosa, como no aguantas la curiosidad abres nuevamente la puerta y ahora si que crees que sucede cuando entras?...exactamente, nuevamente entras a tu casa...que harías si quieres volver a la calle?

Gonzalo
Gonzalo
21

Para entender que es la recursividad primero hay que entender que es la recursividad

Conduda
Conduda
22

Hola, me han ayudado bastante todos los ejemplos y explicaciones, pero aun me queda una duda, ¿Cuántos tipos de recursividad existen?

RULYSavge
RULYSavge
23

La recursividad aunque ayuda en muchos problemas es un poco tediosa, tambien que te ner cuidado pues cuando trabajas con la recursividad pues caer en un algritmo sin fin

HrE
HrE
24

me ha encantado tu artículo, es de hace tiempo pero me ha servido mucho para entender un poco más la recursividad... estoy empezando con ella y aún no he aprendido a "cambiar el chip" gracias

Jose Luis
Jose Luis
25

Segun se oodemos distinguir dos tipos de recursividad: Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente. Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros. saludos a todos

Jose Luis
Jose Luis
26

Tambien existe otra foma de clasificar los tipos de recursividad, que seria: 1. Recursividad Lineal. Máximo una llamada recursiva por rama del condicional y se divide a su vez en; a) Por la cola. b) No por la cola. 2. Recursividad No Lineal. Mas de una llamada recursiva y se divide a su vez en; a)En cascada b)Anidada Espero que con esto se aclaren las dudas en cuanto a los tipos de recursividad. Un saludo a todos

carlitosucv
carlitosucv
27

panas si pudieran subir codigos de ejemplos de recursividad... que no sean los basicos

moc
moc
28

interesado, mira que eres interesado xD http://www.emezeta.com/articulos/backtracking-volviendo-atras aqui está la práctica que quieres. deberias saber buscar! xD

Yesid
Yesid
29

@Viktor: podrias enseñarme como pasar de algoritmos recursivos a iterativos porfavor lo necesito con urgencia

DANIEL
DANIEL
30

bueno gracias papaaa la verdad me ayudo mucho esta buenisimo el blog me gusto el ejemplo de rickymax01 ta bueno bueno se cuidan

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.