Cita de: $Edu$ en 29 Noviembre 2012, 19:35 PM
Por las dudas te digo que yo no he entrado a la universidad por lo que algunas cosas no he aprendido aun, no se bien que es la prueba de escritorio, me podrias explicar si quieres.
Cuando el metodo es llamado recursivamente lo que hace ejecutar la funcion de nuevo pero los valores que tenia antes tomados en la funcion anterior quedan guardados en la memoria para que se usen luego. Es complicado explicarte porque para entender todo sin que te quedes con ninguna duda tendrias que aprender el lenguaje ASM para ver como funcionan los programas a nivel del procesador.
Pero por ahora solo te puedo dar un ejemplo de una funcion recursiva para que entiendas mejor.
La funcion para saber el factorial de un numero se puede hacer con un bucle, seguramente lo has hecho alguna vez, donde vas guardando la variable del numero y lo multiplicas por el numero anterior y a ese nuevo numero lo multiplicas por el anterior y todo asi, por ejemplo el factorial de 4 seria 4 * 3 * 2 * 1 y en tu programa harias un bucle con la variable i que vaya desde 4 a 1 donde vas guardando los resultados de las multiplicaciones y vas multiplicando por i hasta que i sea 1 o 2 total al multiplicar por 1 no cambia y se termina el bucle y la funcion.
Pero lo bueno de los metodos recursivos viene aca.. el factorial de 4 (llamemosle 4!) es igual a 4*3! no? y 3! (factorial de 3) se puede calcular 3 * 2! y 2! sabemos que es 2 * 1 que es 2. Entonces al usar un metodo recursivo la funcion solamente quedaria asi:
Factorial(n) {
if n=2 return 2; ' devuelve 2 y sale de la funcion
return n * Factorial(n - 1) ' como en el ejemplo si n es 4 entonces multiplica 4 por factorial de 3.
}
Entonces como se llama de nuevo en medio de la multiplicacion.. el return no sabe que devolver hasta que se termine la funcion Factorial que se envio como parametro el numero 3. Y vuelve el ciclo de nuevo, comprobando si n es igual a 2 y como no lo es se multiplica 3 * Factorial(2) ahora, porque n ya no es mas 4 ahora es 3, pero de nuevo el return "espera" el valor de Factorial(2) para devolver resultado a la multiplicacion. Pero en Factorial(2) ahora n vale 2 asi que devuelve 2 y ya se sabe el primer valor "base".
Asi que ahora que se llego a la base, vuelve todo para arriba poniendo los valores de los returns desde la base hasta el primero que se llamo, asi que Factorial(3) va a devolver como decia 3 * Factorial(2) que es 6. Y Factorial(4) va a devolver 4 * Factorial(3) que como Factorial(3) dio como resultado 6 entonces 4 * 6 es 24 y se termina la funcion.
Una vez que entiendas eso, que por cierto, te puse el codigo asi nomas, ya que no se PHP pero queria darte una mano de todas formas, podras entender mejor como poder hacer tu algoritmo de las 8 reinas usando Backtracking. Fijate que sin una condicion como la que hice de if n= 2 return 2; la funcion no funcionaria porque quedara buscando un valor continuamente y se generaria un bucle infinito que consumiria toda la ram.
Entonces ahora ponte a pensar que si haces una funcion recursiva donde la llamada a la misma funcion es dentro de un bucle casi no tiene sentido, ya que si haces que devuelva un valor la funcion dentro del for, solo devolvera un valor cuando recien comienza, cuando la variable i del bucle for vale 0. Por eso no sirve para eso, una funcion recursiva llamada dentro de un bucle no tendria significado, por lo menos que yo sepa, me puse a pensar en algun ejemplo y lo termine borrando porque no tenia logica asi que no vale la pena complicarse la vida pudiendolo hacer de otra forma.
Pero si es que sirve para algo, en alguna funcion que no devuelva nada, que se encargue de mostrar un mensaje talvez (por eso digo que no tiene sentido hacerlo asi ya que no devolvera nada entonces no vale la pena hacerlo recursivo pudiendo hacer que repita ese mensaje las veces que quieras en un bucle) la variable i quedara con ese valor esperando que se llegue a la base para despues que "suba" hasta la primer llamada seguir aumentando otra vez su valor haciendo repetir todo de nuevo, se te podrian generar miles de bucles sin sentido pero bueno, tu preguntaste xD
Para hacer uso de backtracking tendras que tener un metodo principal y otros que se encargaran de hacer un movimiento y verificar si es un movimiento valido.
Como resolverias el problema de las 8 reinas en un papel con lapicera? yo lo que hice fue poner una cruz en la primer posicion, alla abajo de todo en la izquierda, luego puse otra cruz en la siguiente columna pero tuve q ponerla 2 posiciones mas arriba para que no se crucen, no la puse mas de 2, solo lo minimo posible, lo mismo para la tercera y para las siguientes ya que sino se cruzaban. En la quinta columna comenze de nuevo desde abajo, la primera posicion no podia porque estaba ocupada por la primer cruz que hice, pero la segunda si asique puse una cruz ahi, luego en la sexta columna fui mirando si podia desde la posicion de abajo de todo hasta arriba hasta que encontre una que si, la septima lo mismo, siempre probando desde la posicion de abajo hasta arriba, pero ya la octaba columna no pude poner ninguna, asi que use el backtracking en mi cabeza y dije, borrare la ultima cruz que puse (dar un paso atras) y vere si tenia otro lugar donde ponerla sin perder, siempre siguiendo probando desde la posicion de abajo hacia arriba, para seguir un orden. Y no habia otra posicion asi que borre la anterior a esa tambien para buscar otro lugar para ponerla y tampoco, todo asi tienes que seguir hasta que encuentres una cruz que puedes cambiarla para poder empezar a avanzar otra vez y ver si llegas a una solucion, si no llegas vuelves de nuevo para atras de la misma forma, desde la ultima cruz hasta que puedas usar otra posicion nueva en alguna cruz para volver otra vez a avanzar xD
Si lo haces con papel y lapiz como te lo redacte entenderas como funciona. La cosa es que yo cuando estaba queriendo hacer uno de esos ejercicios, pero en vez de el de las reinas era el del caballo, esas posiciones que sabia que no iban a tener solucion las iba agregando en arrays para no pasar por ellas, pero era un caos total, si usas backtracking haciendo tu funcion principal recursiva, lograras hacerlo, trata de pensarlo bien y puedes dejar tu idea. Mucho papel y lapicera necesitaras para escribir codigos y algoritmos antes de empezar a programarlo. Saludos!
Muchas gracias, gracias a tu explicacion ahora tengo la idea mucho mas clara....
Pero tengo una ultima pregunta, sabes como puedo medir la eficiencia de este algoritmo (Notacion asintotica)?
