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.

Let's say you define foo() that calls foo(). You then say bar = foo and define a new foo(). When you call bar(), it calls the other foo, not itself. You might say that the function is recursive because it calls a function that has its name, but it could be a different function with the same name. — zondo
– zondo, Commented Apr 16, 2016 at 9:03
@AlexHall: yet that's the only way to check for recursion in Python, when it actually is happening. Because the name used for the recursive call can at any moment be rebound to something else. — Martijn Pieters
– Martijn Pieters, Commented Apr 16, 2016 at 9:06
@MartijnPieters at the very least a solution for OP's problem can be found that works in most cases. zondo's objection is very specific and doesn't necessarily matter to OP. — Alex Hall
– Alex Hall, Commented Apr 16, 2016 at 9:15
@Arthur.V: the answer is that it cannot be done. It can only be guessed at. Static analysis of highly dynamic code is always limited to guessing. The only way to know is to trace (which is what the answers in the duplicate do). — Martijn Pieters
– Martijn Pieters, Commented Apr 16, 2016 at 9:17
You could do it at runtime by setting recursion limit to say 100 and then running a the function for a value that ought to do 500 recursions; see it fail, and then restore recursion limit and see that it returns the correct value — Antti Haapala
– Antti Haapala, Commented Apr 16, 2016 at 10:19

Alex Hall · Accepted Answer · 2016-04-16 10:39:43Z

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.

Jonathan1609 · Accepted Answer · 2021-06-30 15:38:25Z

1

from inspect import stack

already_called_recursively = False


def test():
    global already_called_recursively
    function_name = stack()[1].function
    if not already_called_recursively:
        already_called_recursively = True
        print(test())  # One recursive call, leads to Recursion Detected!

    if function_name == test.__name__:
        return "Recursion detected!"
    else:
        return "Called from {}".format(function_name)


print(test())  # Not Recursion, "father" name: "<module>"


def xyz():
    print(test())  # Not Recursion, "father" name: "xyz"


xyz()

The output is

Recursion detected!
Called from <module>
Called from xyz

I use the global variable already_called_recursively to make sure I only call it once, and as you can see, at the recursion it says "Recursion Detected", since the "father" name is the same as the current function, which means I called it from the same function aka recursion.

The other prints are the module-level call, and the call inside xyz.

Hope it helps :D

answered Jun 30, 2021 at 15:38

Jonathan1609

1,9371 gold badge9 silver badges24 bronze badges

1 Comment

cards Over a year ago

but it detects recursion if called from the body of a recursive function... no inspection for that is needed

JaonHax · Accepted Answer · 2020-09-22 20:59:37Z

I have not yet verified for myself if Alex's answer works (though I assume it does, and far better than what I'm about to propose), but if you want something a little simpler (and smaller) than that, you can simply use sys.getrecursionlimit() to error it out manually, then check for that within a function. For example, this is what I wrote for a recursion verification of my own:

import sys

def is_recursive(function, *args):
  try:
    # Calls the function with arguments
    function(sys.getrecursionlimit()+1, *args)
  # Catches RecursionError instances (means function is recursive)
  except RecursionError:
    return True
  # Catches everything else (may not mean function isn't recursive,
  # but it means we probably have a bug somewhere else in the code)
  except:
    return False
  # Return False if it didn't error out (means function isn't recursive)
  return False

While it may be less elegant (and more faulty in some instances), this is far smaller than Alex's code and works reasonably well for most instances. The main drawback here is that with this approach, you're making your computer process through every recursion the function goes through until reaching the recursion limit. I suggest temporarily changing the recursion limit with sys.setrecursionlimit() while using this code to minimize the time taken to process through the recursions, like so:

sys.setrecursionlimit(10)
if is_recursive(my_func, ...):
  # do stuff
else:
  # do other stuff
sys.setrecursionlimit(1000) # 1000 is the default recursion limit

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related