UTNianos

Versión completa: Consulta - Recursividad e iteracion
Actualmente estas viendo una versión simplificada de nuestro contenido. Ver la versión completa con el formato correcto.
Ayer en un parcial, en un V o F, habia un punto que decia:

"La recursividad es una forma de implementar la iteracion"

Yo puse F, porque la iteracion es una estructura de control basica y la recursividad es una capacidad de las funciones de ser llamadas a si mismas, por lo que en esencia son cosas muy distintas.

El flaco me puso mal, supuestamente era verdadera. Para mi ya de entrada el punto era medio ambiguo, pero bueno.

Me gustaria saber que opinan ustedes.

Gracias.
Si aplicás la misma función varias veces estás iterando te guste o no.
Tal cual! Si bien la implementacion de una cosa y otra sea algo totalmente distinto (uno es una estructura de control: while, for... y la otra es llamar a una función a si misma) en si, a simple vista, parecen 2 cosas distintas pero en el fondo hacen lo mismo. Es como dicen arriba, cuando haces recursividad estas iterando tantas veces como se pueda, un ciclo while se hace tantas veces se pueda, todo dependiendo de las condiciones. La verdad muy engañoso ese V o F...
Tanto los ciclos como la recursividad son diferentes implementaciones de una iteración, por ejemplo en Haskell que es un lenguaje funcional no tiene ciclos while ni for, por lo tanto se aplica recursividad para iterar.
(29-11-2013 23:33)Baron Bomadil escribió: [ -> ]Tanto los ciclos como la recursividad son diferentes implementaciones de una iteración, por ejemplo en Haskell que es un lenguaje funcional no tiene ciclos while ni for, por lo tanto se aplica recursividad para iterar.

en serio? no tienen while? ni me quiero imaginar programar en esa cosa
(29-11-2013 23:33)Baron Bomadil escribió: [ -> ]Tanto los ciclos como la recursividad son diferentes implementaciones de una iteración, por ejemplo en Haskell que es un lenguaje funcional no tiene ciclos while ni for, por lo tanto se aplica recursividad para iterar.

En realidad no existen dichos ciclos como tales, sino mas bien aparecen de forma implicita en ciertos metodos/funciones, es decir en sus implementaciones.
(30-11-2013 01:55)rihardmarius escribió: [ -> ]en serio? no tienen while? ni me quiero imaginar programar en esa cosa

Lo vas a tener que hacer en Paradigmas de programación. Para el paradigma funcional se usa Haskell, y Haskell no usa estructuras de control como los lenguajes imperativos. Se usan mucho (MUCHO) las funciones recursivas, composición de funciones, aplicación parcial de funciones, etc.
El gran problema es que en Algoritmos todavía estás a años luz de poder creer que una función puede manejarse como si fuera un dato.

Te voy a pedir un acto de fe: creeme que podrías tener una variable "de tipo función". Es decir, bajo determinadas circunstancias, podrías hacer algo como lo que escribo abajo, en un lenguaje que no existe (la sintaxis no es la de ningún lenguaje que conozca), pero que no dista mucho de una implementación real:



function siguiente(x) {
return x + 1;
}

function anterior(x) {
return x - 1;
}

function main() {
tipo_funcion algunaFuncion; // declaro una variable de tipo función
algunaFuncion = siguiente; // le asigno a esa variable la función siguiente
print algunaFuncion(2); // imprimo el resultado de llamar a la función que "guardé" en algunaFuncion con el parámetro 2
// osea, imprime "3"

algunaFuncion = anterior; // ahora algunaFuncion pasa a representar a la funcion "anterior"
print algunaFuncion(2); // ahora imprime 1 - porque la que se ejecuta es anterior(2), y ya no siguiente(2)
}




Otra vez: este lenguaje NO existe, pero en los lenguajes "reales" sería MUUUUY parecido el código final (la implementación en C es muy muy parecida).


Si me creés todo esto (vas a aprenderlo en Paradigmas, en su momento), podríamos definir una función for que reciba como parámetro un número y una función: el número va a ser la cantidad de veces que queremos que se ejecute la función. Por ejemplo:



function for(cantidad, funcion) {
if(cantidad > 0) { // tengo que ejecutar "cantidad" veces
for(cantidad - 1, funcion); // ejecuto recursivamente for, con cantidad decrementado
// entonces, en algún momento, de tanto decrementar cantidad va a ser 0, y el if de
// la línea anterior va a cortar. Hasta que eso pase, sigo llamando recursivamente

funcion(cantidad); // una vez que salí del for, ejecuto la función pasándole cantidad
// como parámetro
}
}

function imprimir(x) {
print x; // imprimo el parametro
}

function imprimirSiguiente(x) {
print x + 1;
}

function main() {
tipo_funcion unaFuncion;
unaFuncion = imprimir;
for(20, unaFuncion); // imprime el 1, el 2, el 3, etc, hasta imprimir el 20

unaFuncion = imprimirSiguiente;
for(20, unaFuncion); // imprime el 2, el 3, el 4, etc, hasta imprimir el 21
}





Mi for está hardcodeadísimo (solo funciona generando rangos desde 1 hasta el límite), pero es una "prueba de concepto". Podríamos hacer un for que reciba 4 funciones: estadoInicial, condicionDeCorte, postIncremento y cuerpoDelCiclo (la que veníamos llamando "funcion"), y haciendo algo MUY parecido a esto podríamos implementar "el for de C" recursivamente.


De hecho, en Paradigmas vas a ver otro lenguaje *hermoso* llamado Smalltalk en el que el for es "una función", el if es otra, y "todo excepto las asignaciones" son "funciones" (se usa otra terminología y blah, pero de momento quedate con eso).


Tiempo al tiempo, che =)

PD: quizás hoy no entiendas nada, quizás sí, no lo se. Pero este "apunte" puede servirte para leer algo sobre todo el chamuyo que te tiré =) http://uqbar-wiki.org/index.php?title=Orden_Superior
URLs de referencia