有没有办法检查函数在python中是否递归? [英] Is there a way to check if function is recursive in python?

问题描述

我想为一个练习编写一个测试函数，以确保一个函数被正确实现.
所以我想知道，给定一个函数foo"，有没有办法检查它是否是递归实现的?
如果它封装了一个递归函数并使用它，它也很重要.例如:

I want to write a testing function for an exercise, to make sure a function is implemented correctly.
So I got to wonder, is there a way, given a function "foo", to check if it is implemented recursively?
If it encapsulates a recursive function and uses it it also counts. For example:

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

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

This should also be considered recursive.
Note that I want to use an external test function to perform this check. Without altering the original code of the function.

推荐答案

解决方案:

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

Essentially test_recursion takes a callable with no arguments, calls it, and returns True if at any point during the execution of that callable the same code appeared twice in the stack, False otherwise. I think it's possible that it'll turn out this isn't exactly what OP wants. It could be modified easily to test if, say, the same code appears in the stack 10 times at a particular moment.

这篇关于有没有办法检查函数在python中是否递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！