English subtitles

← Recursion in Other Languages - Intro to Computer Science

Get Embed Code
4 Languages

Showing Revision 6 created 05/25/2016 by Udacity Robot.

  1. Manuel had a question.
  2. "I always though recursive calls were more efficient that iterative functions.
  3. Professor Evans said that recursive definition isn't very efficient in Python.
  4. So I want to ask if other programming languages like C or Java
  5. improve the recursive calls in order to always be more efficient that the iterative method."
  6. Thanks for the question, Manuel.
  7. The problem with recursion in terms of performance is that when you execute
  8. a procedure that does a recursive call you've got to keep track of the state of that call.
  9. That's called a stack frame. You're keeping track of the function you called.
  10. You're keeping track of where to return when you're done,
  11. and you're making a new space to store the parameters that you passed in to that procedure.
  12. If you have a recursive call, each time you're doing the recursive call
  13. you need a new stack frame to keep track of that.
  14. When you finally get to the base case, then you're got a result,
  15. and you've got to unwind all that.
  16. You're going back through all those stack frames, passing back the results,
  17. reclaiming that space. That take a lot of space.
  18. If there are a lot of recursive calls like some of the examples you've seen in 101,
  19. you're going to run out of space when you do that on a high input.
  20. For some languages there's an optimization that the interpreter or the compiler does
  21. to know that if the only thing that you do with the results of the recursive call
  22. is pass it back to the next level, you don't really need to keep track of all those stacks.
  23. You can keep reusing the one you had, just replacing the parameters,
  24. and know that when you're done that's the actual result.
  25. Or maybe you do a more complex optimization where there's something you need
  26. to do on the result, but you don't need to keep track of all those stack frames.
  27. This is what most languages that are designed to use recursion frequently do.
  28. Languages like Lisp and Scheme are designed this way--
  29. to make it very efficient to do recursive calls.
  30. It's still more expensive than iteration, because you still need to do the call.
  31. You need to do the mechanics of calling a procedure and getting a result,
  32. but with this tail recursion optimization,
  33. you don't need to keep track of all those stack frames.
  34. It's much more efficient than it is in Python.
  35. There have been a lot of questions about why am I covering recursive procedures
  36. if they're so inefficient in Python.
  37. The reason for doing that is really it's a very useful way of thinking,
  38. even if you need to eventually turn the procedure into an iterative version of it.
  39. By writing the recursive version and understanding how they recursive definition works
  40. and understanding things that way, you're thinking in a new and powerful way.
  41. Recursive procedures are often easier to reason about than iterative ones.
  42. And if you use a language that does provide tail recursion elimination,
  43. then the recursive definition is often the one that you want to use.
  44. In Python that's usually not the case.
  45. It's better to write a procedure not to have a recursive call,
  46. because you're going to run out of stack space if you ever call it on a large input.