英文:
Python recursive call overhead - RecursionError result before reaching the specified limit by setrecursionlimit
问题
我正在尝试创建一个基本的幂递归函数basicpower
,作为我的大学作业的一部分。我尝试使用sys.setrecursionlimit(100)
来设置递归深度限制为100。当我调用basicpower
并传入任何在98到100之间的值时,它会显示RecursionError: maximum recursion depth exceeded in comparison
错误。然而,如果我调用basicpower
并传入任何在1到97之间的值,它运行得非常正常。是什么导致了这种调用栈的过度?为什么我不能使用由sys.setrecursionlimit
指定的完整数字?
基本幂函数的代码:
import sys
sys.setrecursionlimit(100)
def basicpower(x, n):
'''计算整数n的幂x**n。'''
if n == 0:
return 1 # 基本情况,没有基本情况的话,我们的递归函数将永远运行
else:
return x * basicpower(x, n-1) # 我们的递归调用,因此我们在一个较小的问题空间上调用函数本身
print(basicpower(2, 98))
英文:
I am trying to make a basic power recursive function basicpower
as a part of my university assignment. I tried to set the recursion limit to 100 using sys.setrecursionlimit(100)
. When I make a call to basicpower
with any value between 98 and 100 if shows me a RecursionError: maximum recursion depth exceeded in comparison
error. However, if I make a call to basicpower
with any value between 1 and 97 it works perfectly fine. What causes this overhead in the call stack? Why I can not use the whole number specified by sys.setrecursionlimit
?
Code of basic power function:
import sys
sys.setrecursionlimit(100)
def basicpower(x, n):
'''Compute the value x**n for integer n.'''
if n == 0:
return 1 # base case without base case our recursive function will run forever
else:
return x * basicpower(x, n-1) # our recursive call so we are calling the function on itself on a smaller problem space
print(basicpower(2,98))
答案1
得分: 1
首先要指出的是,因为您将最后一个检查设置为n==0,所以递归调用的总堆栈将为n+1。 n为98已经有99个堆栈。
在此之后,关于细节我不太确定,因为涉及到一些我从未深入研究过的Python底层功能。但是,sys.setrecursionlimit
简单地确定了Python解释器的总堆栈限制。你可以改进你的递归如下:
def basicpower(x, n):
'''计算整数n的x的值。'''
if n == 1:
return x # 基本情况,没有基本情况的话,我们的递归函数将永远运行
else:
return x * basicpower(x, n - 1) # 我们的递归调用,所以我们在一个较小的问题空间上调用函数本身
这将减少递归调用完成所需的堆栈数量。如果你需要在setrecursionlimit
也是100的情况下达到100,如果你的课程允许,你可能可以这样做:
if n == 2:
return x * x
当然,如果你试图实际执行这个操作,只需使用 x**n
更好。
你实际上可以检查函数的现有堆栈。
import inspect
for item in inspect.stack():
print(item)
print(len(inspect.stack()))
在Python脚本或Python控制台中运行此代码,您将获得堆栈长度为1,帧为:
# 对于Python控制台
[FrameInfo(frame=<frame at 0x000001803C38EC00, file '<stdin>', line 1, code <module>>, filename='<stdin>', lineno=1, function='<module>', code_context=None, index=None)]
在.ipynb文件中运行代码将得到堆栈长度为22,而在Google Colab中运行代码将得到堆栈长度为28。不确定这些数字是否会有所变化,但这演示了你开始递归的初始点不会在0,而会根据你使用的Python类型而有所不同。
英文:
So something to point out first, since you have your last check as n==0, your total stack for the recursive call will be n+1. an n of 98 is already 99 stacks.
After this, I'm not too sure about the details since it involves some underlying functionalities of python that I've never looked into. However, sys.setrecursionlimit
is simply determining the total stack limit of the python interpreter. You can improve your recursion as
def basicpower(x, n):
'''Compute the value x**n for integer n.'''
if n == 1:
return x # base case without base case our recursive function will run forever
else:
return x * basicpower(x, n-1) # our recursive call so we are calling the function on itself on a smaller problem space
This would reduce the amount of stacks required by the recursion call to complete by 1. If you are required to be able to get to 100 while the setrecursionlimit is also 100, you my be able to do this if its allowed by your course.
if n==2:
return x*x
Of course, if you are trying to do this practically, simply doing x**n
would be better.
You can actually check the existing stack for your functions.
import inspect
for item in inspect.stack():
print(item)
print(len(inspect.stack()))
Running this in a python script or the python console, you get a stack length of 1 and a frame of
# for python console
[FrameInfo(frame=<frame at 0x000001803C38EC00, file '<stdin>', line 1, code <module>>, filename='<stdin>', lineno=1, function='<module>', code_context=None, index=None)]
Running the code in a .ipynb file gives a stack length of 22, and running it in google colab gave me a stack length of 28. Not sure if these numbers will vary, but this demonstrates how the initial point where you start your recursion won't be at 0, and can vary based on what type of python you are using.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论