CODEWITHSUNDEEP
pythonunit-testingrecursioninspect
mike rodent
mike rodent

Reputation: 15692

Detect that a method is recursive without calling it?

This may sound like a stupid thing to want to achieve. The context is Test-Driven Development: I have a method which involves stepping down through the nodes of a tree, and to develop this function I have gone:
"look at child nodes"
"if child node has children, then look at grandchild nodes"
"if grandchild node has children, then look at great-grandchild nodes"... etc.

And so you get to a point where you have to replace this code with a recursive method. If you are using TDD you want to write an assertion statement which fails if your method is not recursive. This may sound silly to non-TDD people, but one point is that trees typically involve quite a lot of recursive functionality, so it actually feels "bad" to skip this sort of test step!

I'm wondering if the inspect module might have what I need... but I'm struggling. It seems to me that in an ideal world you would want to detect this recursiveness without actually having to call the method.

Upvotes: 1

Views: 576

Answers (2)

Shaunak
Shaunak

Reputation: 18026

Even when doing 'TDD' , its not a good idea to check if method is recursive. Think about it, even if you could find out that method was recursive there are a thousand things that could be wrong with that recursive code.

Instead when doing TDD, come up with small but good representations of data-set you will be processing, and write up cases to check weather the function you are writing handles them well.

Lets consider a example of recursive function to parse and find a sum total of tree nodes. 

def total(tree):
    if tree == None: return 0
    return total(tree.left) + total(tree.right) + tree.cargo

Here are some of the test data cases I would consider to test functionality and not test implementation of function:

Positive Tests to ensure totals are correct

  1. When I have one node in tree is the total correct
  2. When I have one node and two first level children , is the total correct
  3. When I have only one third level right child (left child is missing) is the total correct . .

Then test some Exit conditions:

  1. Init the test with a sample tree, and check if your function exits on the expected node according to algorithm you wish to implement . .

Add some negative tests

  1. Check for thrown exceptions if there are loops in the tree structure . .

and so on... until you have covered some basic combinations. Up two 2 levels deep.

Now you know for these tests to pass, your function will have to do the right thing, recursion or not. And that is a purpose of a unit test. To test functionality and not details of implementation.

Once you are confident that your tests are robust, and any function that passes these tests is a good function, it is inconsequential how that function was implemented. It may or may not be recursive, but you shoudn't care while writing unit tests.

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1124718

You cannot reliably check if a function uses recursion, no.

A simple recursive function would look up a global function with the same name and call that, so you'd have to look at the function bytecode or parse the bytecode into an AST and try and find a call to a global object with the same name. But if a method was being used or the function was aliased, you'll have a much harder task of detecting this.

Besides, you normally test the functionality, not the specific implementation, of the object under test. Test for desired results, not how you produced those.

Perhaps you wanted to avoid recursion, because you may run out of stack. In that case you'd test if you'll run out of stack.

Set the stack depth to a small number (with sys.setrecursionlimit()), create a tree that has more levels than stack, and try and parse it. If a RuntimeError exception is thrown, you were using recursion or another method that relies on the Python call stack too much.

Upvotes: 3

Related Questions