python递归函数错误RuntimeError：超过最大递归深度

Question

我有这个脚本：def number_of_occurences(c, message):  position = message.find(c)  if position == -1:    return 0  else:    if len(message[position:]) == 0:      return position    else:      return position + number_of_occurences(c, message[position:])number_of_occurences('a', 'azertya')但是当我运行它时，我得到这个错误：Traceback (most recent call last):  File "frequency_analysis.py", line 31, in <module>    number_of_occurences('a', 'azertya')  File "file_name.py", line 29, in number_of_occurences    return position + number_of_occurences(c, message[position:]).........  File "file_name.py", line 29, in number_of_occurences    return position + number_of_occurences(c, message[position:])RuntimeError: maximum recursion depth exceeded而且我知道这个类似的问题，但是它没有帮助，花费了更长的时间，但是给出了相同的错误：sys.setrecursionlimit(10000)还有这个：sys.setrecursionlimit(30000)但是为此：sys.setrecursionlimit(50000)它给出了这个错误：分段故障（核心已转储）我在这里做错了什么？提前致谢。

Answer 1

这里是正确的代码：

def number_of_occurences(c, message):

  position = message.find(c)

  nbr = 0.0

  if position == -1:

    return 0

  else:

    nbr += 1

    if len(message[position:]) == 0:

      return nbr

    else:

      return nbr + number_of_occurences(c, message[position + 1:])

Answer 2

问题在于您使用相同的参数递归调用自己，从而保证了无限递归。设置递归限制有多高都没有关系。您无法将其设置为无穷大。*

使用您的参数手动跟踪它。

position = message.find(c) # = 'azertya'.find('a') = 0

if position == -1: # Nope

else:

    if len(message[position:]) == 0: # len('azertya'[0:]) == len('azertya') == 7 != 0

    else:

        return position + number_of_occurences(c, message[position:])

            # 0 + number_of_occurences('a', 'azertya'[0:])

            # == 0 + number_of_occurences('a', 'azertya')

            # which is exactly what we were called with

即使不以第一个字符开头，也可以以字符串中的任何字符开头，但最终还是会遇到相同的问题。同样，尝试使用'r'代替代替进行跟踪'a'。

通过像交互式可视化器运行这一个是比手动跟踪简单得多（和漂亮，更难以拧向上）。

或者，尝试print荷兰国际集团出来c，message和position通过每一次，它应该是很明显这是怎么回事。

解决方法非常简单：

return position + number_of_occurences(c, message[position+1:])

*即使可以，即使堆栈与堆冲突，至少与CPython冲突，也会出现段错误。这就是为什么只有50000出现段错误的原因。但是即使采用其他实现，例如Stackless或PyPy，一旦没有空间容纳更多的堆栈帧，也会出现内存错误。但是，如果您有无限的寻址空间和无限的虚拟页表空间，那么这不是问题，并且愿意永远等待……这仍然行不通，但是至少它永远不会失败。