递归调用和堆栈 [英] Recursive calls and stack
问题描述
我有一个程序可以轻易找到与
点重叠的对象。水平和垂直搜索从
内部递归调用。
这种实现方式是用本地
变量填充堆栈空间在每次通话中。如果这不好，有没有更好的方法实现？b $ b？或者python本身会理解调用在最后一行发生了
，所以局部变量不需要被推入
堆栈？
def find_point（pt）：
返回_hor_search（pt，random_obj）
def _hor_search（pt，obj）：
...
object = ...
...
如果物品满足某些条件：
返回对象
else：
返回_ver_search（pt，object）
def _ver_search（pt，obj）：
...
object = ...
...
如果对象满足某些条件：
返回对象
否则：
返回_hor_search（pt，object）
-
Suresh
En Wed，2007年2月14日03:09:37 -0300， jm ******* @ no.spam.gmail.com
< jm ***** **@gmail.comescribió：
我有一个程序，它可以找到重叠
点的对象。水平和垂直搜索从
内部递归调用。
这种实现方式是用本地
变量填充堆栈空间在每次通话中。如果这不好，有没有更好的方法实现？b $ b？或者python本身会理解调用在最后一行发生了
，所以局部变量不需要被推入
堆栈？
我恐怕没有，调用将被堆叠，直到找到一些对象。
Python不做尾递归优化" （至少，我不知道
）。但即使它可以做到这一点，在这种情况下你会在两个函数之间进行递归
调用，而且这有点难度。
回到你原来的问题，也许你可以从计算几何中使用一些已知的
算法;从
http://www.faqs.org开始/ faqs / graphics / algorithms-faq /
-
Gabriel Genellina
2月14日上午11:45，Gabriel Genellina < gagsl ... @ yahoo.com.ar>
写道：
En Wed，2007年2月14日03:09:37 -0300，jm.sur ... @ no.spam.gmail.com
< jm.sur ... @gmail.comescribió：
我有一个程序可以识别出与
点重叠的对象。水平和垂直搜索从
内部递归调用。
这种实现方式是用本地
变量填充堆栈空间在每次通话中。如果这不好，有没有更好的方法实现？b $ b？或者python本身会理解调用在最后一行发生了
，所以局部变量不需要被推入
堆栈？
我不敢，调用将被堆叠，直到找到一些对象。
Python不做尾递归优化" （至少，我不知道
）。但即使它可以做到这一点，在这种情况下你会在两个函数之间进行递归
调用，而且这有点难度。
回到你原来的问题，也许你可以从计算几何中使用一些已知的
算法;从 http://www.faqs.org/faqs/graphics开始/ algorithms-faq /
-
Gabriel Genellina
谢谢Gabriel的回复。
我可以将电话堆叠起来，但我想知道当前的
变量是否堆叠，因为返回语句后跟着
函数调用？
def test（）：
x = 22
y = 33
z = x + y
返回anotherFunction（z）
在此函数中将所有局部变量（x，y，z）在调用anotherFunction（z）之前将其推入堆栈中，或者Python会发现
不再需要本地人，因为anotherFunction（z）只是
退回？
-
Suresh
2月14日，上午11:09，jm.sur ... @ no.spam.gmail.com
< jm.sur ... @ gmail.comwrote：
我有一个程序可以识别重叠的对象
点。水平和垂直搜索都是从
内部递归调用的。
这种实现方式是用每个调用中的本地
变量填充堆栈空间。如果这不好，有没有更好的方法实现？b $ b？ Orpython自己会理解最后一行调用发生了
，所以不需要将局部变量推入堆栈吗？
def find_point（pt）：
返回_hor_search（pt，random_obj）
def _hor_search（pt，obj）：
...
object = ...
...
如果物品满足某些条件：
返回物品
否则：
返回_ver_search（pt，object）
def _ver_search（pt，obj）：
...
object = ...
...
如果物品满足某些条件：
返回物品
else：
返回_hor_search（pt，object）
-
Suresh
我找到了一个更简单的解决方案：摆脱递归调用;使用时
循环。
-
Suresh
Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?
def find_point(pt):
return _hor_search(pt, random_obj)
def _hor_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _ver_search(pt, object)
def _ver_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _hor_search(pt, object)
-
Suresh
En Wed, 14 Feb 2007 03:09:37 -0300, jm*******@no.spam.gmail.com
<jm*******@gmail.comescribió:
Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?I''m afraid not, the calls will be stacked until some object is found.
Python does not do "tail recursion optimization" (at least, I''m not aware
of that). But even if it could do that, in this case you have recursive
calls between two functions, and that''s a bit harder.
Going back to your original problem, maybe you can use some known
algorithms from computational geometry; start with
http://www.faqs.org/faqs/graphics/algorithms-faq/
--
Gabriel Genellina
On Feb 14, 11:45 am, "Gabriel Genellina" <gagsl...@yahoo.com.ar>
wrote:En Wed, 14 Feb 2007 03:09:37 -0300, jm.sur...@no.spam.gmail.com
<jm.sur...@gmail.comescribió:
Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill the stack space with the local
variables inside each call. If this is not good, is there a better way
to implement? Or python itself will understand that the calls happen
in the last line, so local variables need not be pushed into the
stack?
I''m afraid not, the calls will be stacked until some object is found.
Python does not do "tail recursion optimization" (at least, I''m not aware
of that). But even if it could do that, in this case you have recursive
calls between two functions, and that''s a bit harder.
Going back to your original problem, maybe you can use some known
algorithms from computational geometry; start with http://www.faqs.org/faqs/graphics/algorithms-faq/
--
Gabriel GenellinaThanks Gabriel for the response.
I am OK with calls being stacked, but I wondering will the local
variables be stacked given that return statement is followed by the
function call?
def test():
x = 22
y = 33
z = x+y
return anotherFunction(z)
In this function will all the local variables (x,y,z) be pushed into
the stack before calling anotherFunction(z) or Python will find out
that the locals are no longer needed as anotherFunction(z) is just
returned?
-
Suresh
On Feb 14, 11:09 am, "jm.sur...@no.spam.gmail.com"
<jm.sur...@gmail.comwrote:Hi,
I have a program which literately finds the object that overlapping a
point. The horizontal and vertical search are called recursively from
inside each other.
Is this way of implementation fill thestackspace with the local
variables inside eachcall. If this is not good, is there a better way
to implement? Orpythonitself will understand that the calls happen
in the last line, so local variables need not be pushed into thestack?
def find_point(pt):
return _hor_search(pt, random_obj)
def _hor_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _ver_search(pt, object)
def _ver_search(pt, obj):
...
object = ...
...
if object meets some condition:
return object
else:
return _hor_search(pt, object)
-
SureshI found a simpler solution: get rid of recursive calls; using while
loops.
-
Suresh
这篇关于递归调用和堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
