1

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.

mike rodent
  • 14,126
  • 11
  • 103
  • 157
  • What happens to the test result when someone implements a (correct) tree traversal function using a stack? Are you sure this is what you want to test? – loopbackbee Aug 04 '15 at 16:15
  • 2
    You normally test the *functionality*, not the specific implementation. – Martijn Pieters Aug 04 '15 at 16:16
  • 1
    Why do you care whether it's implemented recursively or not? – jonrsharpe Aug 04 '15 at 16:17
  • @goncalopp sorry, I don't really understand what you mean... – mike rodent Aug 04 '15 at 16:22
  • @jonsharpe: according to the TDD methodology/philosophy I'm trying to adopt, every new step of application code must start with a failed assertion! I don't in fact care whether it's recursive. A traversal approach could be taken, but I'm just trying to find a test which fails if a method is not recursive... – mike rodent Aug 04 '15 at 16:24
  • @mikerodent yes, I'm familiar with TDD, but normally you would write a test that fails because *the required **functionality** is incomplete*. If you later refactor the precise implementation (e.g. to or from a recursive method), that *shouldn't change the test result* (unless your refactoring breaks it!) – jonrsharpe Aug 04 '15 at 16:36
  • Note also that *"so you get to a point where you have to replace this code with a recursive method"* is not accurate - all recursive code can be written iteratively and vice-versa (see e.g. http://stackoverflow.com/q/2093618/3001761), although which is more performant/readable/your criterion here will vary by task. – jonrsharpe Aug 04 '15 at 16:42
  • @jonsharpe thanks for that interesting comment. In fact, in the use case, I only explore the child nodes if the parent is expanded (this is JTree and I'm using Jython), so it's not a case of comprehensive exploration of the tree. Which doesn't of course make it any more likely that recursion is better than traversal, point taken! Maybe what I need to do is create a Traverser which takes account of the expanded/collapsed state of the nodes... food for thought. – mike rodent Aug 04 '15 at 16:56
  • TDD philosophy aside, in Python I believe you would have to call a method to determine if it is recursive. See also: https://stackoverflow.com/questions/7900345/can-a-python-method-check-if-it-has-been-called-from-within-itself – ryanwebjackson Feb 27 '19 at 15:54

2 Answers2

3

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.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • Thanks... I'm new to TDD and trying to teach myself, partly using the book "TDD Using Python". This book distinguishes between "functional testing" and "unit testing". And the author characterises the difference by saying functional testing tests things from the application user's PoV, whereas unit testing tests things from the programmer's PoV. The "philosophy" of this book is that ***every*** step of development (ideally) should first start with a failed test. It's hard, but it seems to produce robust outcomes! BTW, I don't particularly want to avoid recursion. – mike rodent Aug 04 '15 at 16:21
  • @mikerodent: how your function is implemented *doesn't matter* to either focus. The end user doesn't care, they just want a working program. And to keep your tests flexible, you want your unit tests to only test the functionality, not the specific implementation. That way you can swap out implementations easily and still test the new implementation with the existing tests. – Martijn Pieters Aug 04 '15 at 16:23
  • Thanks, this makes sense. – mike rodent Aug 04 '15 at 16:29
0

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.

Shaunak
  • 17,377
  • 5
  • 53
  • 84