python - 有没有办法检查函数在 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 次。