Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales
 Autor
|
Tema: Verdad que es imposible el algoritmo numero primo sin usar ciclos, ni funciones. (Leído 1,923 veces)
|
|
Aikanáro Anário
|
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.
|
|
|
|
|
En línea
|
|
|
|
$Edu$
 Desconectado
Mensajes: 1.413
|
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?
|
|
|
|
|
En línea
|
Estado en el MSN:  |
|
|
pucheto
Desconectado
Mensajes: 214
|
Los ciclos y la recursion son equivalentes.
|
|
|
|
|
En línea
|
|
|
|
|
Aikanáro Anário
|
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?
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.
|
|
|
|
|
En línea
|
|
|
|
pucheto
Desconectado
Mensajes: 214
|
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.
|
|
|
|
|
En línea
|
|
|
|
Khronos14
Desconectado
Mensajes: 285
A lie is a lie
|
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.
|
|
|
|
|
En línea
|
|
|
|
ukol
Desconectado
Mensajes: 31
|
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.
Los ciclos y la recursion son equivalentes.
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.
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. 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.
Utiliza una función que diga si un numero es divisible por alguno de los anteriores a otro numero, divisible(x, num) = mod(x,num) == 0 || divisible(x, num-1)
primo(x) = no(divisible(x,x-1))
Dejo como ejercicio la condición de parada
|
|
|
|
|
En línea
|
|
|
|
|
[Case]
|
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.
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.
|
|
|
|
|
En línea
|
|
|
|
ukol
Desconectado
Mensajes: 31
|
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.
|
|
|
|
|
En línea
|
|
|
|
pucheto
Desconectado
Mensajes: 214
|
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. Ahi te respondiste a vos mismo, usando una pila y listo.
|
|
|
|
|
En línea
|
|
|
|
|
Ragnarok
|
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.
|
|
|
|
|
En línea
|
|
|
|
someRandomCode
Desconectado
Mensajes: 40
|
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  |
|
|
|
|
En línea
|
|
|
|
|
 |
