Manuel had a question.
"I always though recursive calls were more efficient that iterative functions.
Professor Evans said that recursive definition isn't very efficient in Python.
So I want to ask if other programming languages like C or Java
improve the recursive calls in order to always be more efficient that the iterative method."
Thanks for the question, Manuel.
The problem with recursion in terms of performance is that when you execute
a procedure that does a recursive call you've got to keep track of the state of that call.
That's called a stack frame. You're keeping track of the function you called.
You're keeping track of where to return when you're done,
and you're making a new space to store the parameters that you passed in to that procedure.
If you have a recursive call, each time you're doing the recursive call
you need a new stack frame to keep track of that.
When you finally get to the base case, then you're got a result,
and you've got to unwind all that.
You're going back through all those stack frames, passing back the results,
reclaiming that space. That take a lot of space.
If there are a lot of recursive calls like some of the examples you've seen in 101,
you're going to run out of space when you do that on a high input.
For some languages there's an optimization that the interpreter or the compiler does
to know that if the only thing that you do with the results of the recursive call
is pass it back to the next level, you don't really need to keep track of all those stacks.
You can keep reusing the one you had, just replacing the parameters,
and know that when you're done that's the actual result.
Or maybe you do a more complex optimization where there's something you need
to do on the result, but you don't need to keep track of all those stack frames.
This is what most languages that are designed to use recursion frequently do.
Languages like Lisp and Scheme are designed this way--
to make it very efficient to do recursive calls.
It's still more expensive than iteration, because you still need to do the call.
You need to do the mechanics of calling a procedure and getting a result,
but with this tail recursion optimization,
you don't need to keep track of all those stack frames.
It's much more efficient than it is in Python.
There have been a lot of questions about why am I covering recursive procedures
if they're so inefficient in Python.
The reason for doing that is really it's a very useful way of thinking,
even if you need to eventually turn the procedure into an iterative version of it.
By writing the recursive version and understanding how they recursive definition works
and understanding things that way, you're thinking in a new and powerful way.
Recursive procedures are often easier to reason about than iterative ones.
And if you use a language that does provide tail recursion elimination,
then the recursive definition is often the one that you want to use.
In Python that's usually not the case.
It's better to write a procedure not to have a recursive call,
because you're going to run out of stack space if you ever call it on a large input.
Manuel tiene una pregunta
"Siempre pensé que las llamadas recursivas eran más eficientes que las funciones iterativas..
El profesor Evans dijo que la definición
recursiva no es muy eficiente en Python.
Quiero saber si otros lenguajes de
programación, como C ó Java,
manejan las llamadas recursivas de manera tal que siempre sean más eficientes que el método iterativo".
Gracias por la pregunta, Manuel.
El problema con recursión en términos de
desempeño es que cuando ejecutamos..
una procedimiento que hace una llamada recursiva, Ud. tiene que recordar el estado de la llamada.
Esto es llamado un Marco de pila. Ud. tiene que tener en cuenta la función que lo llamó...
tiene que tener en cuenta de donde regresar los resultados cuando acabe..
y tiene que crear un espacio de memoria nuevo para guardar los parametros que le pasó a esa función.
Si hace una llamada recursiva,
cada vez que hace la llamada recursiva
Ud. necesita un Marco de Pila nuevo
para llevar la cuenta de todo esto.
Cuando, finalmente, llega al caso base,
Ud. ya tiene su resultado
y ahora tiene que deshacer todo eso:
tiene que retroceder a travez de todos esos marcos de pila, pasando los resultados hacia atras..
reclamando el espacio.
Todo esto tomá mucha memoria.
SI se hacen muchas llamadas recursivas, como es el caso en algunos de los ejemplos que vimos en 101..
se le va a acabar la memoria cuando
la función reciba un valor grande.
Algunos lenguajes usan una optimización que el interprete, ó compilador, hace:
es saber que si lo único que Ud. hace con
los resultados de la llamada recursiva
es pasarlos hacia atras al siguiente nivel, entonces Ud. realmente no necesita llevar la cuenta de esos marcos.
En cambio Ud. reusa el que ya tiene,
simplemente reemplazando los parámetros,
y ya sabe que cuando acabe, ese es el resultado.
Ó tal vez Ud. hace una optimización más compleja donde hay algo que Ud. necesita hacerle..
al resultado, pero no necesita llevar
la cuenta de todos esos marcos.
Esto es lo que hacen la mayoría de lenguajes diseñados para hacer uso frecuente de recursión.
Lenguajes como Lisp ó Scheme
fueron diseñados de esa manera..
para hacer las llamadas recursivas muy eficientes.
Aun así es más costosa que la iteración porque Ud. aun necesita hacer la llamada,
i.e., necesita ir sobre los pasos de llamar el procedimiento y obtener los resultados..
pero con esta optimización, con recusión de cola,
Ud. ya no necesita llevar la
cuenta de todos esos marcos.
Esto es mucho más eficiente
de lo que lo es en Python.
Hán habido muchas preguntas del porque
estamos viendo procedimientos recursivos..
si son tan ineficientes en Python.
La razón es que está es una
manera de pensar muy util,
inclusive en el caso en el que, eventualmente, vaya a necesitar reescribir el procedimiento iterativamente.
El proceso de escribir la versión recursiva y entender como funciona la definición recursiva.
y el poder entender procesos de esa manera... Ud. va a estar pensando de una manera nueva y poderosa.
Frecuentemente es más facil razonar un
problema recursivamente que uno iterativo..
Y, si está usando un lenguaje
que tiene recursión de cola,
entonces la recursión iterativa es,
frecuentemente, la que Ud. quiere usar.
Con frecuencia, este no es el caso en Python.
Es mejor escribir un procedimiento
que no haga una llamada recursiva..
porque se le acabará el espacio de marcos en el momento en que Ud. la llame con un valor grande.
マニュエルさんからの質問です
“再帰呼び出しは繰り返し関数よりも効率的だと
ずっと思っていましたが”
“エヴァンス教授のお話では”
“再帰定義はPythonでは
あまり効率的でないとのことでした”
“そこで質問ですが
CやJavaのようなプログラミング言語では”
“再帰呼び出しの方が繰り返し処理よりも
効率的になりますか?”
マニュエルさん 質問をありがとうございます
パフォーマンスの点で見た再帰の問題は
再帰呼び出しを行う関数を実行した時に
その呼び出しの状態を
保持しなければならないことです
それをスタックフレームと呼びます
呼び出した関数を保持して
終了した時に返すべき場所を保持して
関数に渡したパラメータを格納するために
新しいスペースを作ります
再帰呼び出しがある場合は 再帰呼び出しを行う度に
それを保持するための
新たなスタックフレームが必要になります
最終的に基本ケースに達した時に結果を得ると共に
すべてを解放しなければなりません
すべてのスタックフレームを1つずつ調べ直し
結果を返してスペースを再生するのです
これには多くのスペースが必要です
CS101で学んだ例のように
多くの再帰呼び出しがある場合は
大きな入力でそれを行うと
スペースを使い果たしてしまいます
言語によっては
インタプリタやコンパイラが最適化を行ってくれます
その最適化とは
再帰呼び出しの結果を次のレベルに返すだけなら
すべてのスタックは保持しないということです
パラメータを置き換えることで
既存のスタックを再利用し続けることができて
処理が終了した時にそれが実際の結果となるのです
結果を使って何かを行う必要がある場合は
さらに複雑な最適化が行われるでしょうが
すべてのスタックフレームを保持する必要はありません
再帰をよく使うように設計された言語では
大抵このような仕組みになっています
例えばLispやSchemeのような言語は
再帰呼び出しを大変効率的に行えるように
設計されています
それでも繰り返しよりはコストが高くなります
呼び出しはやはり必要となるからです
関数を呼び出して結果を取得するという過程が
必要となります
ですがこの末尾再帰最適化を使えば
すべてのスタックフレームを
保持する必要はありません
これはPythonの場合よりもはるかに効率的です
Pythonで効率の悪い再帰関数を
なぜ取り上げるのかという質問がたくさんありました
再帰を取り上げたのは
考え方として非常に役に立つからです
最終的に繰り返しの関数に変換する必要は
あるかもしれませんが
再帰を使って書き再帰定義が
どのように機能するのかを理解することで
新しく効果的な考え方ができるようになります
再帰関数は繰り返しを使うものよりも
論理的に考えやすい場合が多いと思います
末尾再帰除去を提供する言語を使う場合は
再帰定義を使用した方がよい場合が多いでしょう
ですがPythonでは通常はそうなりません
再帰呼び出しのない関数を書いた方がいいでしょう
大きな入力で呼び出した場合に
スタックスペースを使い果たしてしまうからです
Manuel 提出一個問題
"我總是認為遞迴呼叫比反覆運算的函式
更有效率
Evans 教授說,遞迴定義在 Python 中並不是很有效率
所以我想問問,其他程式語言如 C 或 Java
是否為了能比反覆運算方法更有效率,改善了遞迴呼叫?"
Manuel,謝謝你的問題
遞迴在性能方面的問題是,當你執行一個做遞迴的程序
你要跟蹤呼叫的狀態
那稱為堆疊框 (stack frame),
你要跟蹤你所呼叫的函式 (function)
你要跟蹤:當你做完函式,返回原來程式的位置
你要有新的空間
來儲存你傳入該程序的參數
如果你有遞迴呼叫,每次做遞迴呼叫時
你需要新的堆疊框 (stack frame) 來記錄這些值
當你終於到達基本情況時,你得到了結果
然後你要捲回這一切
你要回到所有這些堆疊框 (stack frame),傳回結果
回收這些空間,這需要很大的空間
如果有很多遞迴呼叫,像你在 101 看到的例子
當你以很多輸入作執行時,你的空間會不足
對某些語言,其解譯器 (interpreter) 或編譯器 (compiler)
會做最佳化 (optimization)
它會知道,你處理遞迴呼叫的結果只是
把它傳回到下一個層級,你不需要真的追蹤所有的堆疊
你可以不斷地再次使用你擁有的堆疊,只要替換參數
而且知道當你完成時,得到了真正的結果
或者也許你做了更複雜的最佳化 (optimization)
那裏有對結果需要做的東西
但是,你不需要跟蹤所有這些堆疊框 (stack frame)
這是大多數語言,為了使用遞迴,經常會做的事
像 Lisp 和 Scheme 語言就是這樣的設計方式
使得執行遞迴呼叫的效率很高
因為你仍然需要做呼叫,所以仍然比反覆運算來得昂貴
你需要做呼叫程序和獲取結果的機制
但是使用這種尾部遞迴最佳化
(tail recursion optimization)
你不需要跟蹤所有的堆疊框 (stack frame)
它是比 Python 更為有效率
有很多的疑問關於遞迴程序
如果它在 Python 中沒有效率,
為什麼我要將它涵蓋進來呢?
這樣做的原因是,它真的是非常有用的思考方式
即使你最後需要把程序,變成反覆運算的版本
透過寫遞迴版本,並瞭解遞迴定義是如何運作
並運用這種方式來理解事情,
你正以又新又強大的方式做思考
遞迴程序往往比反覆運算更容易了解
如果你使用的語言,
它確實消除了尾部遞迴 (tail recursion)
那麼,遞迴定義往往是你想要使用的方法
在 Python ,通常不是這個情況
寫的程序裡,最好沒有遞迴呼叫
因為如果你呼叫它時,用了很大的輸入,
你會用完堆疊空間