I need to find all functions in a Python project which are recursive (i.e. call themselves). Any ideas how to approach this?
2 Answers
It's hard to say whether function recursive or not before it runs. I would personally use this one with inspect.getclosurevars (added in Python 3.3):
import sys
if sys.version_info >= (3, 3, 0):
from inspect import getclosurevars
def is_recursive(func):
if sys.version_info >= (3, 3, 0):
return getclosurevars(func).globals.get(func.__name__) is func
else:
# We can implement part of it if it's not in our standard library
def global_vars_in_closure(func):
vars = {x: func.__globals__.get(x) for x in func.__code__.co_names}
return vars
return global_vars_in_closure(func).get(func.__name__) is func
It will work correctly in most use cases, just remember to use func_X instead of __X__ as function methods on Python 2. It will fail only if a function contain a reference to itself without call:
def false_recursive():
false_recursive
def true_recursive():
true_recursive()
assert is_recursive(true_recursive), 'Must not fail'
assert not is_recursive(false_recursive), 'See? It fails' # AssertionError: See? It fails
2 Comments
aruisdante
Note that this won't detect the case where the function was passed itself from outside, and will false-positive in cases where for example the function returns (but does not call) itself or passes itself to some other function/class. There isn't really a general way to detect recursion with 100% certainty pre-runtime in a language with first-class function objects. But for the purpose of what I assume is an assignment, this will probably work.
Matthew Trevor
It will also give a false positive if the function is mentioned in comments or docstrings, which can be fairly common with doctest et al.
You can parse the source code with ast:
code = """
def f(x):
f(x)
def g(x):
pass
"""
import ast
class FindRecursiveFunctions(ast.NodeVisitor):
def __init__(self):
self._current_func = None
self.recursive_funcs = set()
def generic_visit(self, node):
if node.__class__ is ast.FunctionDef:
self._current_func = node.name
if node.__class__ is ast.Call and node.func.id == self._current_func:
self.recursive_funcs.add(self._current_func)
super(FindRecursiveFunctions, self).generic_visit(node)
>>> tree = ast.parse(code)
>>> finder = FindRecursiveFunctions()
>>> finder.visit(tree)
>>> finder.recursive_funcs
set(['f'])
1 Comment
Blckknght
While this is a generally elegant solution, it can be broken if you have any nested function definitions. For example, move the definition of
g into the f function before the recursive call, and the recursion won't be detected any more. I'd also expect that you'd get false positives if you define a nested function, then call it (from the outer function).
inspectmight be applicable.pycallgraph, see here