c ++中的递归函数行为

Question

我知道递归函数的基本定义.....但我想知道它对内存的影响？为什么不选择循环或迭代？

Answer 1

通常不会出于以下两个原因之一选择它:

• 编码器不理解递归(特别是尾端优化); 和
• 它在堆栈空间上可能很昂贵.

虽然标准对堆栈空间没什么好说的,但它往往是一个容易溢出的有限资源.

例如,这是一个糟糕的递归函数:

def addTwoPositiveNumbers (a,b):
    if b == 0:
        return a
    return addTwoPositiveNumbers (a+1,b-1)

(除非它可以做尾部优化).那是因为它理论上可以使用大量的堆栈级别,例如,当b = 1,000,000,000它使用十亿个堆栈帧时.

另一方面,二进制搜索也不算太差,因为它会在每个递归级别中删除一半的搜索空间.因此,即使您有十亿个条目,也只能记录_2个 1,000,000,000或30个堆栈级别.

列出了我认为人们避免它的原因,我应该说我使用它很多,你应该意识到许多问题自然表达为一种递归解决方案.代码更清晰,更易读.仅仅因为这个原因,它应该是你的武器库的一部分.