CODEWITHSUNDEEP
c#crecursion
HATEM EL-AZAB
HATEM EL-AZAB

Reputation: 371

Why do static variables not allow recursion?

As mentioned in Concept of Programming Languages book by Sebesta:

Why do static variables not support recursion? Is this because if recursion takes place it will waste a lot of memory because it is static and that means it will not deallocated from memory until the complete program terminates?

Upvotes: 9

Views: 11598

Answers (4)

Michael Buen
Michael Buen

Reputation: 39393

Perhaps some example code can give an illustration how memory is managed when using recursion. And how using static variable in a recursive routine is a no-starter(one possible exception is when you want a global counter for counting how many times a function is called, regardless of how the method was called(e.g. from multi-threaded or consecutive call))

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

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, the values can survive in between calls. This is not desirable if you want to divide-and-conquer a given problem, especially on multi-threaded method invocations. If two simultaneous calls is done on callMe method, the other callMe might not be able to complete its task as the these method invocations are just using the same variable instance(static variables), these method invocations will have side effect to each other, these methods can't work independently of each other, as they don't have independent copy of variables.

The code above even it's not multi-threaded, the next method invocation won't be able to finish its task, as the second invocation access the same variable (static variable) and receive value that was tainted already by previous method invocations

In simplistic terms, static variables even it's inside a function, is still a global variable. static variables inside a function just prevent name collisions, but for all intents and purposes, static variables are global variables

To make the code perform as intended, change the if (i < 10) to if (j < 10)

By the way, non-static variables are allocated their own memory, it's allocated on the stack. If we don't have stopping condition, after many recursive calls, the code above will yield stack overflow error, this is where stackoverflow got its name. Suffice to say, programmers are fond of recursion ツ

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

Upvotes: 5

Eric Lippert
Eric Lippert

Reputation: 659956

What makes static fields difficult to use in recursive algorithms is not that they are static but that they are not associated with an activation. Non-static fields are equally difficult to use effectively in a recursive algorithm.

Moreover, the problem is not that it is hard to use fields with recursive algorithms, but more generally that it is hard to use fields with re-entrant algorithms, or algorithms where the same code is going to be called on multiple threads.

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

In short: the book is confusing because it is too specific. It's like saying that it's difficult to balance a brown egg on a white table; that is true, but what do brown and white have to do with it? 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-entrancy scenario.

Upvotes: 19

phatfingers
phatfingers

Reputation: 10250

Recursion layers multiple instances of an object, with each instance preserving its own data. A static variable is shared across all instances. I'm certain a static variable can be used by a recursive process, and would be appropriate when used as a constant, but can make debugging difficult when used dynamically.

Upvotes: 2

Kyle Jones
Kyle Jones

Reputation: 5532

Each recursive call will be accessing the same static variable, overwriting values stored in the variable by other calls. That's not generally desired when doing recursion unless the static variable is serving some purely iterative purpose, e.g. counting the number of times the function was called.

Upvotes: 9

Related Questions