Search for recursive functions in a Python project

Question

I need to find all functions in a Python project which are recursive (i.e. call themselves). Any ideas how to approach this?

Answer 1

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

Answer 2

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'])