有没有办法检查 python 中函数是否递归？

Question

我想为练习编写一个测试函数，以确保函数被正确实现。
所以我想知道，给定一个函数"foo"，有没有办法检查它是否递归实现？
如果它封装了一个递归函数并使用它，它也算在内。例如：

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

这也应该被认为是递归的。
请注意，我想使用 external 测试函数来执行此检查。不改变函数的原始代码。

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)

示例usage/tests：

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 接受一个不带参数的可调用对象，调用它，并且 returns True 如果在执行该可调用对象的任何时候相同的代码在堆栈中出现两次, False 否则。我认为这可能不是 OP 想要的。它可以很容易地修改以测试，比如说，相同的代码是否在特定时刻在堆栈中出现 10 次。

Answer 2

我还没有亲自验证 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

Answer 3

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

有没有办法检查 python 中函数是否递归？

Is there a way to check if function is recursive in python?

python

recursion

python-internals