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