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

Question

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)

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.

Answer 1

Solution:

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)

Example 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

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.