Recursividad: Entender lo entendible

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


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

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

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? ;)

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

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

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

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

Recursividad: Vease "Recursividad"

xD

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?

¿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.

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?

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.

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

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;


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

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.

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...

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

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

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?

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

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

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

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

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

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