Japanese subtitles

← 25-04 Recursion in Other Languages

25-04 Recursion in Other Languages

Get Embed Code
4 Languages

Showing Revision 1 created 07/21/2014 by osawakjvta.

  1. マニュエルさんからの質問です
  2. “再帰呼び出しは繰り返し関数よりも効率的だと
    ずっと思っていましたが”
  3. “エヴァンス教授のお話では”
  4. “再帰定義はPythonでは
    あまり効率的でないとのことでした”
  5. “そこで質問ですが
    CやJavaのようなプログラミング言語では”
  6. “再帰呼び出しの方が繰り返し処理よりも
    効率的になりますか?”
  7. マニュエルさん 質問をありがとうございます
  8. パフォーマンスの点で見た再帰の問題は
  9. 再帰呼び出しを行う関数を実行した時に
  10. その呼び出しの状態を
    保持しなければならないことです
  11. それをスタックフレームと呼びます
  12. 呼び出した関数を保持して
  13. 終了した時に返すべき場所を保持して
  14. 関数に渡したパラメータを格納するために
    新しいスペースを作ります
  15. 再帰呼び出しがある場合は 再帰呼び出しを行う度に
  16. それを保持するための
    新たなスタックフレームが必要になります
  17. 最終的に基本ケースに達した時に結果を得ると共に
  18. すべてを解放しなければなりません
  19. すべてのスタックフレームを1つずつ調べ直し
    結果を返してスペースを再生するのです
  20. これには多くのスペースが必要です
  21. CS101で学んだ例のように
    多くの再帰呼び出しがある場合は
  22. 大きな入力でそれを行うと
    スペースを使い果たしてしまいます
  23. 言語によっては
    インタプリタやコンパイラが最適化を行ってくれます
  24. その最適化とは
    再帰呼び出しの結果を次のレベルに返すだけなら
  25. すべてのスタックは保持しないということです
  26. パラメータを置き換えることで
    既存のスタックを再利用し続けることができて
  27. 処理が終了した時にそれが実際の結果となるのです
  28. 結果を使って何かを行う必要がある場合は
    さらに複雑な最適化が行われるでしょうが
  29. すべてのスタックフレームを保持する必要はありません
  30. 再帰をよく使うように設計された言語では
    大抵このような仕組みになっています
  31. 例えばLispやSchemeのような言語は
  32. 再帰呼び出しを大変効率的に行えるように
    設計されています
  33. それでも繰り返しよりはコストが高くなります
    呼び出しはやはり必要となるからです
  34. 関数を呼び出して結果を取得するという過程が
    必要となります
  35. ですがこの末尾再帰最適化を使えば
  36. すべてのスタックフレームを
    保持する必要はありません
  37. これはPythonの場合よりもはるかに効率的です
  38. Pythonで効率の悪い再帰関数を
    なぜ取り上げるのかという質問がたくさんありました
  39. 再帰を取り上げたのは
    考え方として非常に役に立つからです
  40. 最終的に繰り返しの関数に変換する必要は
    あるかもしれませんが
  41. 再帰を使って書き再帰定義が
    どのように機能するのかを理解することで
  42. 新しく効果的な考え方ができるようになります
  43. 再帰関数は繰り返しを使うものよりも
    論理的に考えやすい場合が多いと思います
  44. 末尾再帰除去を提供する言語を使う場合は
  45. 再帰定義を使用した方がよい場合が多いでしょう
  46. ですがPythonでは通常はそうなりません
  47. 再帰呼び出しのない関数を書いた方がいいでしょう
  48. 大きな入力で呼び出した場合に
    スタックスペースを使い果たしてしまうからです