有没有一种方法来检查函数在python中是否是递归的？

Question

我想为练习编写一个测试函数，以确保一个函数的实现是正确的。

所以我想知道，给定函数"foo"，是否有一种方法来检查它是否是递归实现的？

如果它封装了一个递归函数并使用它，那么它也是计数的。例如：

def foo(n):
    def inner(n):
        #more code
        inner(n-1)
    return inner(n)

这也应该被认为是递归的。

请注意，我希望使用外部测试函数来执行此检查。而不改变函数的原始代码。

Answer 1

解决方案：

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次。

Answer 2

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

Answer 3

我还没有为自己验证过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