Python function to detect and count recursive functions using Abstract Syntax Trees (AST). Detects recursive calls in function return statements and function bodies. Also detects mutual recursion up to 2nd degree (e.g. is_even calling is_odd calling is_even and so on)

count_recursions.py

# helper function to identify recursive functions
def count_recursions(code: str) -> int:
    self_recursion_functions = set()
    mutual_recursion_candidates = {}
    mutual_recursion_functions = set()
    nodes = ast.parse(code)
    function_nodes = []

    # get all function nodes
    for node in nodes.body:
        if isinstance(node, ast.FunctionDef):
            function_nodes.append(node)
            mutual_recursion_candidates[node.name] = set() # init dict

    # check for self recursion functions and mutual recursion candidates
    for node in function_nodes:
        for node_of_function in ast.walk(node):

            # recursive call in function body
            if isinstance(node_of_function, ast.Call):
                if not hasattr(node_of_function.func, "id"):  # skip if function name is not provided
                    continue

                if node_of_function.func.id == node.name:
                    # return statement contains call to its own function => function is recursive
                    self_recursion_functions.add(node.name)
                else:
                    # add function call of return statment to mutual_recursion_candidates
                    try:
                        mutual_recursion_candidates[node_of_function.func.id].add(node.name)
                    except:
                        pass  # could not find called function in function definitions (e.g. built in functions)

            # recursive call in return statement
            if isinstance(node_of_function, ast.Return) and isinstance(node_of_function.value, ast.Call):
                if not hasattr(node_of_function.value.func, "id"): # skip if function name is not provided
                    continue

                # check if return statement contains call to its own function
                if node_of_function.value.func.id == node.name:
                    # return statement contains call to its own function => function is recursive
                    self_recursion_functions.add(node.name)
                else:
                    # add function call of return statment to mutual_recursion_candidates
                    try:
                        mutual_recursion_candidates[node_of_function.value.func.id].add(node.name)
                    except:
                        pass # could not find called function in function definitions (e.g. built in functions)

    # check for mutual recursion functions
    for node in function_nodes:
        for node_of_function in ast.walk(node):
            if isinstance(node_of_function, ast.Return) and isinstance(node_of_function.value, ast.Call):
                if not hasattr(node_of_function.value.func, "id"): # skip if function name is not provided
                    continue

                # check if return statement contains call to its own function
                if node.name in mutual_recursion_candidates[node_of_function.value.func.id]:
                    # functions are mutually recursive
                    mutual_recursion_functions.add(node_of_function.value.func.id)
                    mutual_recursion_functions.add(node.name)

    return len(self_recursion_functions.union(mutual_recursion_functions))