c ++测试以检查函数是否以递归方式实现

Question

对于作业的自动评分，我正在尝试开发一个测试，检查是否以递归方式实现了 c++ 函数。

我目前的想法是：
1) 解析函数代码并检查关键字 {for, while, goto}
2) 以某种方式监视调用堆栈。也许来自不同的线程，或者通过编写 GDB 脚本。

我对其他想法很好奇，或者也许有人已经实施了上述之一。

Answer 1

您可以使用 Clang 的LibTooling来解析 C++ 代码。然后遍历 AST 并构建一个调用图（即以函数作为节点、边作为从一个函数到另一个函数的调用的图）。使用Tarjan 算法在该图中搜索循环。如果存在循环，则可能存在递归实现。

如果代码使用动态分派（即虚拟函数），本文可能会对您有所帮助。如果代码使用函数指针，本文可能会出现这种情况，但一般来说，问题是无法判定的。

如果您只是寻找直接递归，那么扫描函数体 AST 来查找对自身的调用就足够了，但理论上您仍然需要检查动态分派和函数指针。

编辑：请参阅此问题以生成调用图。