是否有可能判断函数是否递归？

是否有任何方式读取和解析文件，以查看函数是否使用for循环与递归来获取其答案？假设它只能是一个或另一个，函数不会引发，并且函数保证结束。是否有可能判断函数是否递归？

2014-10-28 user3475234

在“基本”的条件下，你至少可以告诉我们，如果一个函数直接调用自身：

def test(x): 
    return test(x) 

test.__code__.co_name in test.__code__.co_names # true and co_name can't be changed 
test.__name__ in test.__code__.co_names # true but name can be changed

这用来检查函数的名称是由函数引用的全局名称。

我说“基本”，因为有很多方法可以解决这个问题。 Lambdas没有名字，所以他们不会匹配他们绑定的全球名称。一个函数可以被重命名。内部代码可以为函数引用不同的名称。该函数可以调用第二个函数，这是真正的递归函数。并且...

基本上，没有办法知道函数是递归的。

来源

2014-10-28 04:39:13 davidism

谢谢，这真的非常有帮助，正是我所期待的。有没有办法使用字符串作为函数名称？换句话说，我可以做'nm = coolfunction（test .__ name __）'然后'nm（x）'或类似的东西吗？我觉得像这样，你提到的一些问题可以通过创建一个函数调用图来解决。 – user3475234 2014-10-28 05:23:18

做了一些研究之后，我看到'coolfunction == getattr'。谢谢你的帮助。 – user3475234 2014-10-28 05:31:55

有没有一般的方法来证明一个计算机程序完成（它被证明有程序，你不知道）。幸运的是，实际上有静态分析工具，可以为大多数小程序做到这一点。

此外，对于大多数Python函数来说，它明显具有什么样的复杂性（对于受过教育的程序员而言），或者在文档中提及了使用哪种算法。

如果你对细节感兴趣，你应该阅读一两本有关算法的书。你也可以看看https://cs.stackexchange.com/，这是一个更适合一般讨论不同算法的计算复杂度的网站。

来源

2014-10-28 03:57:39

对不起，如果我不清楚，但这不是问题 - 我说我想使用该程序完成的假设，并且它不是一个不正确的函数。不是为了证明这一点。我想以编程方式确定函数是使用递归还是循环。我意识到这可能是不可能的，但这是真正的问题。我知道你不能以编程方式确定一个函数是否结束，但我想这可能是一个不同的问题（可能通过查看堆栈或其他东西）。 – user3475234 2014-10-28 04:16:43

是否有可能判断函数是否递归？

回答

相关问题