Foro de elhacker.net

Ya para mi era imposible sin ciclos, pero alguien me explicó que con las funciones recursivas sí se puede.

El caso es que debería de hacerlo solo con decisiones.

Al usar funciones recursivas no estas usando funciones? xD

Hablas del algoritmo de saber si es primo o no, o de mostrar los numeros primos hasta n numero?

Los ciclos y la recursion son equivalentes.

Es que dado un numero, diga si es primo o no.

Yo diría que una función recursiva no es en sí un ciclo, o sea porque no es un for, ni un while, ni un do...while, pero sí es un ciclo, o sea sí, pero no.

El caso es que creo no se puede hacer un algoritmo así, solo con decisiones, o si se puede hacer, pero solo hasta determinado número.

Ya lo dije, podes escribir cualquier ciclo, como una funcion recursiva, y cualquier funcion recursiva, como un ciclo. Y se puede demostrar y es facil de demostrar.

Aikanáro Anário, cuando el código se traduce a ensamblador todos los bucles/ciclos se convierten en saltos (tipo goto). Así que técnicamente una función recursiva es un bucle.

Saludos.

No creo que esto sea así, más bien diría que todo ciclo puede hacerse con recursión  pero no al revés. A no ser que uses estructuras de datos recursivas como una pila.

De hecho si eso fuera cierto podría utilizarse CTO(Call tail optimization) siempre, que es covertir una llamada recursiva en un salto goto, o sea un ciclo. O sea que interesaría convertir toda llamada recursiva en un ciclo ya que este no consume espacio en pila y es más eficiente.


Utiliza una función que diga si un numero es divisible por alguno de los anteriores a otro numero,
Dejo como ejercicio la condición de parada

Si es asi, es algo que esta demostrado, toda recursion se puede pasar a un ciclo, y todo ciclo se puede pasar a una recursion.

Por favor citad las fuentes, para lo de la demostración.

Ahi te respondiste a vos mismo, usando una pila y listo.

La máquina de Turing puede hacer cualquier cosa. ¿Tiene ciclos o funciones? Yo diría que no.

Lo único que hace falta es salto condicional.

Es que caemos en lo mismo, un salto condicional hacia arriba que vuelve a repetirse, es un ciclo/bucle.

Porque? imaginense esto
Direccion            Codigo
000001              mov eax,5
000005              add eax,eax
000007              jnz 1

Esto es equivalente a:
for (int x=5;x==0;x++);

Y si quieren encapsularlo en una funcion recursiva, lo mismo, bueno, parecido, agrega un poco de codigo pero el concepto se queda en lo mismo.
Si por ejemplo con gcc/g++ le agregan un -funroll-all-loops para que trate de transformar los ciclos en algo lineal, van a ver que igual cosas como estas se repiten.

Si tenemos una funcion que es recursiva pasa lo mismo, salvo por, bueno, lo que implica como el paso de funciones y de mas, pero en si, la funcion esta siempre en el mismo lugar.

Aun con algunas formas de lenguajes orientados a objetos donde el sistema carga para dos objetos de la misma clase una sola vez la funcion se repite esto. Digo en algunos, porque no se en todos, pero en C++ si pasa, y se pueden fijar mirando el address de un puntero a funcion en dos funciones en dos objetos distintos del mismo tipo.

Me voy a sacar las ganas de preguntarlo en la facu, pero el debate esta bueno, y esta bueno ver sus opiniones, este foro da gusto cuando es asi :)