Chinese, Traditional subtitles

← 06x-04 Recursion in Other Languages

Get Embed Code
4 Languages

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

  1. Manuel 提出一個問題
  2. "我總是認為遞迴呼叫比反覆運算的函式
    更有效率
  3. Evans 教授說,遞迴定義在 Python 中並不是很有效率
  4. 所以我想問問,其他程式語言如 C 或 Java
  5. 是否為了能比反覆運算方法更有效率,改善了遞迴呼叫?"
  6. Manuel,謝謝你的問題
  7. 遞迴在性能方面的問題是,當你執行一個做遞迴的程序
  8. 你要跟蹤呼叫的狀態
  9. 那稱為堆疊框 (stack frame),
    你要跟蹤你所呼叫的函式 (function)
  10. 你要跟蹤:當你做完函式,返回原來程式的位置
  11. 你要有新的空間
    來儲存你傳入該程序的參數
  12. 如果你有遞迴呼叫,每次做遞迴呼叫時
  13. 你需要新的堆疊框 (stack frame) 來記錄這些值
  14. 當你終於到達基本情況時,你得到了結果
  15. 然後你要捲回這一切
  16. 你要回到所有這些堆疊框 (stack frame),傳回結果
  17. 回收這些空間,這需要很大的空間
  18. 如果有很多遞迴呼叫,像你在 101 看到的例子
  19. 當你以很多輸入作執行時,你的空間會不足
  20. 對某些語言,其解譯器 (interpreter) 或編譯器 (compiler)
    會做最佳化 (optimization)
  21. 它會知道,你處理遞迴呼叫的結果只是
  22. 把它傳回到下一個層級,你不需要真的追蹤所有的堆疊
  23. 你可以不斷地再次使用你擁有的堆疊,只要替換參數
  24. 而且知道當你完成時,得到了真正的結果
  25. 或者也許你做了更複雜的最佳化 (optimization)
    那裏有對結果需要做的東西
  26. 但是,你不需要跟蹤所有這些堆疊框 (stack frame)
  27. 這是大多數語言,為了使用遞迴,經常會做的事
  28. 像 Lisp 和 Scheme 語言就是這樣的設計方式
  29. 使得執行遞迴呼叫的效率很高
  30. 因為你仍然需要做呼叫,所以仍然比反覆運算來得昂貴
  31. 你需要做呼叫程序和獲取結果的機制
  32. 但是使用這種尾部遞迴最佳化
    (tail recursion optimization)
  33. 你不需要跟蹤所有的堆疊框 (stack frame)
  34. 它是比 Python 更為有效率
  35. 有很多的疑問關於遞迴程序
  36. 如果它在 Python 中沒有效率,
    為什麼我要將它涵蓋進來呢?
  37. 這樣做的原因是,它真的是非常有用的思考方式
  38. 即使你最後需要把程序,變成反覆運算的版本
  39. 透過寫遞迴版本,並瞭解遞迴定義是如何運作
  40. 並運用這種方式來理解事情,
    你正以又新又強大的方式做思考
  41. 遞迴程序往往比反覆運算更容易了解
  42. 如果你使用的語言,
    它確實消除了尾部遞迴 (tail recursion)
  43. 那麼,遞迴定義往往是你想要使用的方法
  44. 在 Python ,通常不是這個情況
  45. 寫的程序裡,最好沒有遞迴呼叫
  46. 因為如果你呼叫它時,用了很大的輸入,
    你會用完堆疊空間