是否有方法检查函数在python中是否是递归的?

解决方案:

from bdb import Bdb
import sys

class RecursionDetected(Exception):
    pass

class RecursionDetector(Bdb):
    def do_clear(self, arg):
        pass

    def __init__(self, *args):
        Bdb.__init__(self, *args)
        self.stack = set()

    def user_call(self, frame, argument_list):
        code = frame.f_code
        if code in self.stack:
            raise RecursionDetected
        self.stack.add(code)

    def user_return(self, frame, return_value):
        self.stack.remove(frame.f_code)

def test_recursion(func):
    detector = RecursionDetector()
    detector.set_trace()
    try:
        func()
    except RecursionDetected:
        return True
    else:
        return False
    finally:
        sys.settrace(None)

示例用法/测试:

def factorial_recursive(x):
    def inner(n):
        if n == 0:
            return 1
        return n * factorial_recursive(n - 1)
    return inner(x)


def factorial_iterative(n):
    product = 1
    for i in xrange(1, n+1):
        product *= i
    return product

assert test_recursion(lambda: factorial_recursive(5))
assert not test_recursion(lambda: factorial_iterative(5))
assert not test_recursion(lambda: map(factorial_iterative, range(5)))
assert factorial_iterative(5) == factorial_recursive(5) == 120

基本上 test_recursion 获取一个不带参数的可调用函数,调用它,然后返回 True 如果在该可调用代码的执行期间的任何时刻,相同的代码在堆栈中出现两次, False 否则我认为这可能会证明这不是OP想要的。它可以很容易地修改,以测试同一代码是否在特定时刻出现在堆栈中10次。

我还没有亲自验证Alex的答案是否有效(尽管我认为它有效,而且比我即将提出的要好得多),但是如果你想要比这个更简单(更小)的东西,你可以简单地使用 sys.getrecursionlimit() 手动将其错误输出,然后在函数中检查该错误。例如,这是我为自己的递归验证编写的:

import sys

def is_recursive(function, *args):
  try:
    # Calls the function with arguments
    function(sys.getrecursionlimit()+1, *args)
  # Catches RecursionError instances (means function is recursive)
  except RecursionError:
    return True
  # Catches everything else (may not mean function isn't recursive,
  # but it means we probably have a bug somewhere else in the code)
  except:
    return False
  # Return False if it didn't error out (means function isn't recursive)
  return False

虽然它可能不那么优雅(在某些情况下更容易出错),但这是 远的 比Alex的代码小,在大多数情况下都能正常工作。这里的主要缺点是,使用这种方法,你会让你的计算机处理函数所经历的每一次递归,直到达到递归极限。我建议使用 sys.setrecursionlimit() 同时使用此代码最小化处理递归所需的时间,如下所示:

sys.setrecursionlimit(10)
if is_recursive(my_func, ...):
  # do stuff
else:
  # do other stuff
sys.setrecursionlimit(1000) # 1000 is the default recursion limit

from inspect import stack

already_called_recursively = False


def test():
    global already_called_recursively
    function_name = stack()[1].function
    if not already_called_recursively:
        already_called_recursively = True
        print(test())  # One recursive call, leads to Recursion Detected!

    if function_name == test.__name__:
        return "Recursion detected!"
    else:
        return "Called from {}".format(function_name)


print(test())  # Not Recursion, "father" name: "<module>"


def xyz():
    print(test())  # Not Recursion, "father" name: "xyz"


xyz()

输出为

Recursion detected!
Called from <module>
Called from xyz

我使用全局变量 already_called_recursively 确保我只调用它一次,正如你所见,在递归时,它会显示“检测到递归”,因为“父”的名称与当前函数相同,这意味着我从同一个函数调用了它,也就是递归。

其他打印是模块级调用和内部调用 xyz .

希望有帮助:D