Hack x Crack - Comunidad de Seguridad informática

Programación => C / C++ => Mensaje iniciado por: fenix_93 en Marzo 26, 2015, 03:46:44 am

Título: es necesaria la recursividad??
Publicado por: fenix_93 en Marzo 26, 2015, 03:46:44 am
Hola, Estoy aprendiendo lenguaje C y ya llevo un buen tiempo programando en este lenguaje pero aun se me dificulta la recursividad.
Mi pregunta es: Es muy necesario aprender recursividad??? ¿se utiliza muy a menudo?
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 26, 2015, 09:50:04 am
No es necesaria, cualquier algoritmo recursivo se puede reescribir como iterativo, y viceversa.

Sin embargo, muchos problemas se describen más fácilmente con un enfoque recursivo (recorrer todos los directorios de un sistema de ficheros, por ejemplo).

Además, es una herramienta muy potente. En programación funcional se usan funciones recursivas en lugar de bucles.

Cuando interiorices la recursividad, el siguiente paso es la recursividad final (tail recursion en inglés) :-)
Título: Re:es necesaria la recursividad??
Publicado por: fenix_93 en Marzo 27, 2015, 03:53:43 am
ufffff, bueno, muchas gracias. veo que me toca estudiar mucho porque se me dificulta un poco hacer algoritmos por recursividad pero espero q no por mucho tiempo.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 27, 2015, 09:05:13 am
ufffff, bueno, muchas gracias. veo que me toca estudiar mucho porque se me dificulta un poco hacer algoritmos por recursividad pero espero q no por mucho tiempo.

En realidad no es tan difícil. Hay problemas para los que la recursividad es natural. El ejemplo típico es la definición matemática de factorial:
fact(n) = 1 si n es 0
fact(n) = n * fact(n-1) en los demás casos

Otro ejemplo es la exploración de sistemas de ficheros:
Código: [Seleccionar]
int numFicherosDirectorios (Directorio d)
{
    count = 0;
    for each fichero in d
        count++;

    for each directorio dir in d
        count += numFicherosDirectorio(dir);
}

Para explorar árboles, se trata cada nodo como si fuera la raíz de un árbol más pequeño:

Código: [Seleccionar]
]nodo buscarElementoEnArbolBinario(nodo arbol, int elemento)
{
    if (elemento == nodo.valor)
        return nodo;
    else if (elemento < nodo.valor)
        return buscarElementoEnArbolBinario(nodo.izquierda, elemento);
    else // if (elemento > nodo.valor)
        return buscarElementoEnArbolBinario(nodo.derecha, elemento);
}

Si tienes que sumar una lista de valores de un array, también lo puedes hacer recursivamente, pero es absurdo.
Título: Re:es necesaria la recursividad??
Publicado por: Jen en Marzo 27, 2015, 11:18:31 pm
Otro ejemplo típico dónde la solución recursiva es MUCHO más sencilla que la solución iterativa es el de las Torres de Hanoi.
Título: Re:es necesaria la recursividad??
Publicado por: fenix_93 en Marzo 30, 2015, 04:38:00 am
muchas gracias, ya lo he estado estudiando y poco a poco se me facilita
Título: Re:es necesaria la recursividad??
Publicado por: C_printfer en Marzo 30, 2015, 11:59:35 am
La recursividad siempre es difícil. Pero cierto es que a veces, dada la complejidad del problema, es mucho más interesante hacer el código recursivo, ya que incluso se te ocurre antes esa solución que la iterativa.

Y bueno... Eso de que siempre hay una solución iterativa... Me parece demasiado arriesgado afirmar eso jajaja, aunque por ahora creo que todo lo que me he encontrado se podría haber hecho iterativo también.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 30, 2015, 03:20:49 pm
Me parece demasiado arriesgado afirmar eso

Cualquier función recursiva se puede convertir en recursiva final, y la conversión de recursiva final a iterativa es trivial.
Título: Re:es necesaria la recursividad??
Publicado por: StackOverflow en Marzo 31, 2015, 08:55:54 am
Yo diría que la recursividad sólo se usa para fines didácticos, porque en la práctica un programa recursivo puede gastar muchísima memoria y tiempo.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 31, 2015, 09:22:18 am
Yo diría que la recursividad sólo se usa para fines didácticos, porque en la práctica un programa recursivo puede gastar muchísima memoria y tiempo.

Sólo si está mal escrito.
Título: Re:es necesaria la recursividad??
Publicado por: C_printfer en Marzo 31, 2015, 03:13:12 pm
Yo diría que la recursividad sólo se usa para fines didácticos, porque en la práctica un programa recursivo puede gastar muchísima memoria y tiempo.

Te sorprendería a veces ver que con recursividad un programa ocupa 3 líneas de código, sin recursividad, pueden salir 200 o 300.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 31, 2015, 03:26:11 pm
Te sorprendería a veces ver que con recursividad un programa ocupa 3 líneas de código, sin recursividad, pueden salir 200 o 300.

¿Algún ejemplo?
Título: Re:es necesaria la recursividad??
Publicado por: C_printfer en Marzo 31, 2015, 06:19:40 pm
Te sorprendería a veces ver que con recursividad un programa ocupa 3 líneas de código, sin recursividad, pueden salir 200 o 300.

¿Algún ejemplo?

Piensa en un algoritmo que tenga que encontrar el camino más corto entre todos los posibles de un grafo (obviamente, considerando que un camino puede estar compuesto de más de un nodo). El programa debe ser capaz de hacer el cálculo correcto sea cual sea el grafo de entrada, por lo que se desconocen de antemano el número de nodos adyacentes de cada uno, no se conoce nada del grafo que nos pueden dar.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Marzo 31, 2015, 07:15:57 pm
¿Qué más da? Hay que explorarlo igual, ya sea recursiva o iterativamente.
Título: Re:es necesaria la recursividad??
Publicado por: StackOverflow en Abril 01, 2015, 12:58:15 am
Yo diría que la recursividad sólo se usa para fines didácticos, porque en la práctica un programa recursivo puede gastar muchísima memoria y tiempo.

Sólo si está mal escrito.

Digamos que tienes millones de cifras, para hacer una búsqueda y encontrar una cifra no vas a querer utilizar un programa recursivo para esa tarea.
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Abril 01, 2015, 01:34:10 am
Si están ordenadas haría una búsqueda binaria, que es un algoritmo típicamente recursivo.
Título: Re:es necesaria la recursividad??
Publicado por: C_printfer en Abril 01, 2015, 04:17:29 pm
¿Qué más da? Hay que explorarlo igual, ya sea recursiva o iterativamente.

Pues da 300 líneas de código de diferencia. Puedes programarlo si no te convences jeje. Piensa todas las funciones que tendrías que hacer para hacerlo de forma iterativa y todos los casos que se te podrían dar. Pero bueno, no vamos a crear discusión ;)
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Abril 01, 2015, 06:55:27 pm
Pues da 300 líneas de código de diferencia. Puedes programarlo si no te convences jeje. Piensa todas las funciones que tendrías que hacer para hacerlo de forma iterativa y todos los casos que se te podrían dar. Pero bueno, no vamos a crear discusión ;)

¿Por qué no pones la versión recursiva en pseudocódigo? Tengo curiosidad.
Título: Re:es necesaria la recursividad??
Publicado por: doommachine en Mayo 10, 2015, 09:26:30 am
¿especificamente cual es el objetivo de la recursividad? ¿Hacer programas mas rapidos y que consuman menos recursos?
Título: Re:es necesaria la recursividad??
Publicado por: ravenheart en Mayo 10, 2015, 10:43:02 am
No; con un compilador decente, un algoritmo iterativo y uno recursivo (bien escritos, claro) deben de ser equivalentes. Con recursividad es mucho más fácil liarla, porque si el algoritmo no es recursivo final (tail recursion en inglés) las llamadas a funciones se hacen de verdad y la anidación puede ser muy grande, lo que aparte de consumir mucha memoria, fácilmente puede causar un desbordamiento de pila.

La ventaja está en la expresividad; aunque la potencia expresiva real es equivalente, permite enfocar los problemas de otra manera, que a menudo resulta más natural.