Why don't static variables allow recursion?

Question

As mentioned in Sebest's Programming Languages ​​book:

• Static variables provide global access; they can store values ​​between subroutine calls (history-sensitive) and efficient.
• Static variables do not support recursion

Why don't static variables support recursion? Is it because if recursion takes place, it will waste a lot of memory because it is static , which means that it will not be freed from memory until the complete program is completed?

Answer 1

Take a look at Eric Lippert below. This answer pointed to a link that is no longer available, and since it is an accepted answer, I cannot delete it now.

Answer 2

The fact that static fields are difficult to use in recursive algorithms is not that they are static, but that they are not related to activation. Non-static fields are equally difficult to use effectively in a recursive algorithm.

In addition, the problem is not that it is difficult to use fields with recursive algorithms, but more generally it is difficult to use fields with repeated algorithms or algorithms in which the same code will be called on multiple threads.

What makes local variables and formal parameters useful in recursion and other re-entry scripts is that they are associated with activation.

In short: the book is confusing because it is too specific. It looks like it's hard to balance a brown egg on a white table; it's true, but what are brown and white related to this? It is difficult to balance any egg on any table. It is difficult to correctly use a static field in a recursive call, because it is difficult to correctly use any field in any re-entry scenario.

Answer 3

Each recursive call will access the same static variable, overwriting the values ​​stored in the variable with other calls. This is usually not required when performing a recursion if the static variable does not serve any purely iterative purpose, for example. counting how many times the function was called.

Answer 4

Perhaps some sample code can illustrate how memory is managed using recursion. And how is the use of a static variable in a recursive subroutine a non-starter (one possible exception is the need for a global counter to count how many times a function is called, regardless of how the method is called (for example, from multi-threaded or sequential calls))

Given this C code:

 #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(eg 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; } 

Output:

 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 

As we can see, the static i variable has only one location in memory; and as such, values ​​can survive between challenges. This is not advisable if you want to separate and overcome a given problem, especially with multi-threaded method calls. If two methods of simultaneous calling are performed using the callMe method, the other callMe may not fulfill its task, since these method calls simply use the same instance of the variable (static variables), these method calls will have a side effect for each other, these methods will not can work independently of each other since they do not have an independent copy of variables.

In the above code, even if it is not multithreaded, the next method call will not be able to complete its task, since the second call gets access to the same variable (static variable) and gets a value that has been corrupted by previous method calls

In simplified terms, static variables, even inside a function, are still a global variable. static variables inside a function simply prevent name collisions, but for all purposes and tasks static variables are global variables

To make the code run, change the value of if (i < 10) to if (j < 10)

By the way, non-static variables allocate their own memory allocated on the stack. If we do not have a stop condition, then after many recursive calls, the code above will lead to an error, this is where stackoverflow got its name. Suffice it to say that programmers love recursionツ

Live test: http://ideone.com/Xl86q

Answer 5

Recursive layers contain multiple instances of an object, each instance retains its own data. A static variable is used for all instances. I am sure that a static variable can be used by a recursive process and will be useful when used as a constant, but it can make debugging difficult when used dynamically.