c++ test to check if a function is implemented recursively [closed]

Question

for automated grading of assignments I'm trying to develop a test that checks whether a c++ function is implemented recursively.

My current ideas are:
1) parse the function code and check for the keywords {for, while, goto}
2) somehow monitor the call stack. Maybe from a different thread, or by scripting GDB.

I'm curious about other ideas or maybe somebody has already implemented one of the above.

Answer 1

You can use Clang's LibTooling to parse the C++ code. Then walk through the AST and build a call graph (i.e. graph with functions as nodes and edges as calls from one function to another). Search that graph for cycles, using Tarjan's algorithm. If a cycle exists, you have a potentially recursive implementation.

If the code uses dynamic dispatch (i.e. virtual functions), this paper may help you. If the code uses function pointers, this paper might but in general, the problem is undecidable.

If you're only looking for direct recursion, scanning the function's body AST for calls to itself is enough, but theoretically you'd still need to check dynamic dispatch and function pointers.

Edit: See this question for generating a callgraph.