Spanish subtitles

← 06x-04 Recursión en Otros Lenguajes

Get Embed Code
4 Languages

Showing Revision 2 created 08/01/2014 by Fran Ontanaya.

  1. Manuel tiene una pregunta
  2. "Siempre pensé que las llamadas recursivas eran más eficientes que las funciones iterativas..
  3. El profesor Evans dijo que la definición
    recursiva no es muy eficiente en Python.
  4. Quiero saber si otros lenguajes de
    programación, como C ó Java,
  5. manejan las llamadas recursivas de manera tal que siempre sean más eficientes que el método iterativo".
  6. Gracias por la pregunta, Manuel.
  7. El problema con recursión en términos de
    desempeño es que cuando ejecutamos..
  8. una procedimiento que hace una llamada recursiva, Ud. tiene que recordar el estado de la llamada.
  9. Esto es llamado un Marco de pila. Ud. tiene que tener en cuenta la función que lo llamó...
  10. tiene que tener en cuenta de donde regresar los resultados cuando acabe..
  11. y tiene que crear un espacio de memoria nuevo para guardar los parametros que le pasó a esa función.
  12. Si hace una llamada recursiva,
    cada vez que hace la llamada recursiva
  13. Ud. necesita un Marco de Pila nuevo
    para llevar la cuenta de todo esto.
  14. Cuando, finalmente, llega al caso base,
    Ud. ya tiene su resultado
  15. y ahora tiene que deshacer todo eso:
  16. tiene que retroceder a travez de todos esos marcos de pila, pasando los resultados hacia atras..
  17. reclamando el espacio.
    Todo esto tomá mucha memoria.
  18. SI se hacen muchas llamadas recursivas, como es el caso en algunos de los ejemplos que vimos en 101..
  19. se le va a acabar la memoria cuando
    la función reciba un valor grande.
  20. Algunos lenguajes usan una optimización que el interprete, ó compilador, hace:
  21. es saber que si lo único que Ud. hace con
    los resultados de la llamada recursiva
  22. es pasarlos hacia atras al siguiente nivel, entonces Ud. realmente no necesita llevar la cuenta de esos marcos.
  23. En cambio Ud. reusa el que ya tiene,
    simplemente reemplazando los parámetros,
  24. y ya sabe que cuando acabe, ese es el resultado.
  25. Ó tal vez Ud. hace una optimización más compleja donde hay algo que Ud. necesita hacerle..
  26. al resultado, pero no necesita llevar
    la cuenta de todos esos marcos.
  27. Esto es lo que hacen la mayoría de lenguajes diseñados para hacer uso frecuente de recursión.
  28. Lenguajes como Lisp ó Scheme
    fueron diseñados de esa manera..
  29. para hacer las llamadas recursivas muy eficientes.
  30. Aun así es más costosa que la iteración porque Ud. aun necesita hacer la llamada,
  31. i.e., necesita ir sobre los pasos de llamar el procedimiento y obtener los resultados..
  32. pero con esta optimización, con recusión de cola,
  33. Ud. ya no necesita llevar la
    cuenta de todos esos marcos.
  34. Esto es mucho más eficiente
    de lo que lo es en Python.
  35. Hán habido muchas preguntas del porque
    estamos viendo procedimientos recursivos..
  36. si son tan ineficientes en Python.
  37. La razón es que está es una
    manera de pensar muy util,
  38. inclusive en el caso en el que, eventualmente, vaya a necesitar reescribir el procedimiento iterativamente.
  39. El proceso de escribir la versión recursiva y entender como funciona la definición recursiva.
  40. y el poder entender procesos de esa manera... Ud. va a estar pensando de una manera nueva y poderosa.
  41. Frecuentemente es más facil razonar un
    problema recursivamente que uno iterativo..
  42. Y, si está usando un lenguaje
    que tiene recursión de cola,
  43. entonces la recursión iterativa es,
    frecuentemente, la que Ud. quiere usar.
  44. Con frecuencia, este no es el caso en Python.
  45. Es mejor escribir un procedimiento
    que no haga una llamada recursiva..
  46. porque se le acabará el espacio de marcos en el momento en que Ud. la llame con un valor grande.