为什么静态变量不允许递归？

Question

如Sebesta的"编程语言概念"一书所述:

• 静态变量提供全局访问,可以在子程序调用(历史敏感)之间保留值,并且是高效的.
• 静态变量不支持递归

为什么静态变量不支持递归？这是因为如果发生递归会浪费大量内存,因为它就是static并且这意味着在整个程序终止之前它不会从内存中释放出来吗？

Answer 1

使静态字段难以在递归算法中使用的原因并不是它们是静态的,而是与激活无关.非静态字段在递归算法中同样难以有效使用.

此外,问题不在于难以使用具有递归算法的字段,而是更常见的是难以使用具有可重入算法的字段,或者在多个线程上将要调用相同代码的算法.

使局部变量和形式参数在递归和其他重入场景中有用的原因是它们与激活相关联.

简而言之:这本书很混乱,因为它太具体了.这就像说在白色桌子上平衡一个棕色的鸡蛋是很困难的; 这是真的,但棕色和白色与它有什么关系呢？在任何桌子上很难平衡任何鸡蛋.在递归调用中很难正确使用静态字段,因为在任何重入场景中很难正确使用任何字段.

Answer 2

每个递归调用将访问相同的静态变量,通过其他调用覆盖存储在变量中的值.除非静态变量服务于某些纯粹的迭代目的,例如计算函数被调用的次数,否则在进行递归时通常不需要这样做.

Answer 3

也许一些示例代码可以说明使用递归时如何管理内存。以及如何在递归例程中使用静态变量是一个没有启动器（一个可能的例外是，当您想要一个全局计数器来计算函数被调用的次数时，无论该方法是如何调用的（例如，从多线程或连续称呼））

鉴于此 C 代码：

#include <iostream>
using namespace std;


void callMe(int j) {

        static int i = 0;

        ++i;
        ++j;
        printf("Loop: %d\n", i);

        printf("i memory location: %p\n", &i);
        printf("j memory location: %p\n", &j);            
        printf("\n");

        // change i to j ,
        // so the other next method invocations
        // or simultaneous(e.g. multi-threaded) method invocations
        // of this method can work independently from 
        // other method invocations / simultaneous method invocations
        if ( i < 10 ) 
            callMe(j);

        printf("Returning from loop %d\n", j);        
}

int main() {     
        callMe(0);
        printf("Next\n");
        callMe(0);     
        return 0;     
}

输出：

Loop: 1
i memory location: 0x804a038
j memory location: 0xbf8b69c0

Loop: 2
i memory location: 0x804a038
j memory location: 0xbf8b69b0

Loop: 3
i memory location: 0x804a038
j memory location: 0xbf8b69a0

Loop: 4
i memory location: 0x804a038
j memory location: 0xbf8b6990

Loop: 5
i memory location: 0x804a038
j memory location: 0xbf8b6980

Loop: 6
i memory location: 0x804a038
j memory location: 0xbf8b6970

Loop: 7
i memory location: 0x804a038
j memory location: 0xbf8b6960

Loop: 8
i memory location: 0x804a038
j memory location: 0xbf8b6950

Loop: 9
i memory location: 0x804a038
j memory location: 0xbf8b6940

Loop: 10
i memory location: 0x804a038
j memory location: 0xbf8b6930

Returning from loop 10
Returning from loop 9
Returning from loop 8
Returning from loop 7
Returning from loop 6
Returning from loop 5
Returning from loop 4
Returning from loop 3
Returning from loop 2
Returning from loop 1
Next
Loop: 11
i memory location: 0x804a038
j memory location: 0xbf8b69c0

Returning from loop 1

正如我们所见，static i变量在内存中只有一个位置；因此，这些值可以在调用之间保留。如果您想分而治之，这是不可取的，尤其是在多线程方法调用上。如果同时调用两个callMe方法，另一个 callMe 可能无法完成它的任务，因为这些方法调用只是使用相同的变量实例（静态变量），这些方法调用会对彼此产生副作用，这些方法不能彼此独立工作，因为它们没有独立的变量副本。

上面的代码即使不是多线程的，下一个方法调用也无法完成它的任务，因为第二个调用访问相同的变量（静态变量）并接收已经被前一个方法调用污染的值

简单来说，静态变量即使在函数内部，仍然是全局变量。函数内的静态变量只是防止名称冲突，但出于所有意图和目的，静态变量是全局变量

为了使代码预期效果，改if (i < 10)以if (j < 10)

顺便说一下，非静态变量分配了自己的内存，它是在堆栈上分配的。如果我们没有停止条件，经过多次递归调用，上面的代码会产生堆栈溢出错误，这就是stackoverflow的名字。可以说，程序员喜欢递归吗？

现场测试：http : //ideone.com/Xl86q