Understanding the Behavior of Variables When Implementing Recursion

Problem You want to implement recursion in JavaScript, and you also want to understand how variables will behave under those circumstances. Theory In JavaScript, you do not need to declare the variable type, or even declare the variable. For example, the following code works perfectly:

    if( counter == 1) {
    buffer = "counter is 1";
    }
 document.getElementById(  "result").innerHTML = buffer;

The buffer variable was not declared before the if block in the preceding code. The last line of the code uses the buffer variable to assign the innerHTML property. This sort of declaration is problematic because buffer might be undefined. JavaScript will not mention this as an error, and innerHTML will be assigned the value undefined. This example illustrates that variables in JavaScript can behave in ways that a programmer with a Java or C# background may not be accustomed to. The focus of this recipe is on figuring out how a variable behaves in different contexts. One example context is the implementation of recursion in JavaScript. Solution Two example functions that implement recursion in JavaScript follow.

    Source: /website/ROOT/ajaxrecipes/javascript/variablebehavior.html
    function RecursionGlobal( counter) {
    info(  "RecursionGlobal{localCounter}", typeof( localCounter));
    localCounter = counter;
    info(  "RecursionGlobal{localCounter}", localCounter);
    if( localCounter < 3) {
    RecursionGlobal( localCounter + 1);
    }
    }
    function RecursionLocal( counter) {
    info( "RecursionLocal{localCounter}",  typeof( localCounter));
    var localCounter = counter;
    info( "RecursionLocal{localCounter}",  localCounter);
    if( localCounter < 3) {
    RecursionLocal( localCounter + 1);
    }
 }

The example shows two methods: RecursionGlobal and RecursionLocal. Between the two methods there is a single difference, as shown in the bold code: the JavaScript keyword var. The single keyword var is the variation on how the localCounter variable is stored. The behavior of both methods when executed is identical and generates the same result. You may think at first glance that the var keyword does not serve any purpose. But the var keyword does serve a purpose, which is illustrated by running the following program:

    Info:recursion_global *** Started ***
    Info:RecursionGlobal{localCounter} undefined
    Info:RecursionGlobal{localCounter} 1
    Info:RecursionGlobal{localCounter} number
    Info:RecursionGlobal{localCounter} 2
    Info:RecursionGlobal{localCounter} number
    Info:RecursionGlobal{localCounter} 3
    Info:recursion_local *** Started ***
    Info:RecursionLocal{localCounter} undefined
    Info:RecursionLocal{localCounter} 1
    Info:RecursionLocal{localCounter} undefined
    Info:RecursionLocal{localCounter} 2
    Info:RecursionLocal{localCounter} undefined
 Info:RecursionLocal{localCounter} 3

Notice that when the RecursionGlobal function executes, the type of the localCounter for the first call is undefined, and thereafter it is number. In contrast, when the RecurisonLocal function is called, the type of localCounter is undefined for each and every call.

This means that var serves the purpose of declaring a variable that is local to the scope from which it is declared. If the variable is not associated with a var keyword, then the variable is declared in global scope. In the case of creating a recursion loop, you will need to use the var keyword for all cases; otherwise, there could be data corruption. The following example illustrates how to reverse the contents of a stack using recursion. When using recursion, sometimes you will need to declare function parameters that serve no purpose other than as reference values.

    Source: /website/ROOT/ajaxrecipes/javascript/variablebehavior.html
    function RecursiveStackOldWay( arrayToProcess,  processedArray) {
    info( "RecursiveStackOldWay",  "---> Start");
    info( "RecursiveStackOldWay",  "Recursive depth=" + (processedArray.length + 1));
    processedArray.push( arrayToProcess.pop());
    if( arrayToProcess.length > 0) {
    RecursiveStackOldWay( arrayToProcess,  processedArray);
    }
    info( "RecursiveStackOldWay",  "---> End");
    }
    var arrayToProcess = new Array();
    arrayToProcess.push( "value1");
    arrayToProcess.push( "value2");
    var processedArray = new Array()
 RecursiveOldWayStack( arrayToProcess,  processedArray);

Here, the RecursiveStackOldWay function has two parameters: arrayToProcess and processedArray. The first parameter, arrayToProcess, is the array that will be reversed. The second parameter, processedArray, is the destination stack. The destination stack needs to be dragged along as a parameter for each recursion, so that the function can put the stack somewhere. The caller is responsible for instantiating the destination stack and passing it to the recursive function. Often, though, when creating recursive functions, you will need to call the function with certain parameters that are defined in the first top-level call. These parameters have nothing to do with the initial call, yet the first top-level call needs to declare them (processedArray). In a nutshell, the problem is that when calling a recursive function, you need to initialize a set of variables that are then used by the recursion. In the example, the initialization is a responsibility of the caller. The solution works, but it is far from optimal, because the developer needs to understand how certain parameters function, even though they might not be used by the caller. Another solution is to create a wrapper function to the recursion that initializes the parameters and then calls the recursion.

The wrapper function will work, but now the programmer has to maintain the recursion function and the wrapper function. JavaScript offers a third solution: let the recursion function initialize itself. The question is, how does the recursion function know it is being called for the first time? In a traditional programming language like Java or C#, a Boolean parameter would be defined and set to true to indicate the first call, and false to indicate any subsequent call. The JavaScript solution does not require a flag or indicator, because the parameters themselves are indicators. For example, imagine if the RecursiveOldWayStack function implementation stays as is and the code that calls RecursiveOldWayStack resembles the following:

    var arrayToProcess = new Array();
    arrayToProcess.push( "value1");
    arrayToProcess.push( "value2");
 var processedArray = RecursiveOldWayStack(  arrayToProcess);

In the modified implementation, the caller is not responsible for instantiating the destination stack. That responsibility has been delegated to the RecursiveOldWayStack function. However, a problem arises because RecursiveOldWayStack needs to initialize and begin the recursion. The solution used by JavaScript is to determine whether the second parameter is defined, as illustrated in the following modified function called RecursiveStack.

    Source: /website/ROOT/ajaxrecipes/javascript/variablebehavior.html
    function RecursiveStack( arrayToProcess,  processedArray) {
    info( "RecursiveStack", "--->  Start");
    if(  typeof( processedArray) == "undefined") {
    info(  "RecursiveStack", "Initial");
    processedArray  = new Array();
    RecursiveStack(  arrayToProcess, processedArray);
    info(  "RecursiveStack", "---> End");
    return  processedArray;
    }
    else {
    info( "RecursiveStack",  "Recursive depth=" + (processedArray.length + 1));
    processedArray.push( arrayToProcess.pop());
    if( arrayToProcess.length > 0) {
    RecursiveStack( arrayToProcess,  processedArray);
    }
    info( "RecursiveStack", "--->  End");
    return;
    }
 }

In the modified implementation, the RecursiveStack function implements an expectation. The expectation is that if the function is called with a single parameter, then it is a caller doing the first call of the recursion; otherwise, a recursion is happening. The expectation of knowing whether a first call is happening is determined by the code in bold. If the second parameter, processedArray, is undefined, then the recursive function initializes itself and starts the recursion. If the second parameter is defined, then it is assumed a recursion is happening, and the function will process the data as such. Before we continue, you might have caught the fact that RecursiveStack has two parameters, but is being called with one.

Earlier I talked about expectations and that the caller needs to pass two parameters. This example does not say that that the caller does not need to pass two parameters; rather, the example says that if the caller does not pass two parameters, the function has the ability to compensate. The same function can be used for the initialization and recursion based on an expectation. If, however, a caller defines the second parameter, that means the caller has taken on the responsibility to implement the initialization. With a caller-defined initialization, RecursiveStack will not perform an initialization and will jump directly to the recursion functionality.

The advantage of this solution is that you have a multipurpose function without having to explicitly define a wrapper function. You may be thinking, “Of course this is possible using a language such as Java or C# using overloaded functions.” Yes, it is possible using overloaded functions, but as mentioned earlier, an overloaded function is a wrapper function that calls the actual implementation, meaning two functions need to be written and maintained. In JavaScript, everything can be wrapped into one self-contained function. Now that you’ve implemented recursion and know the difference between a locally scoped variable and a globally scoped variable, the next question is, what happens if there are two variables with the same name? Imagine defining a variable at a local scope that exists in a global scope what happens to the globally and locally scoped variable declarations? The following code shows how a variable is defined globally in one function and then referenced in another function.

    Source: /website/ROOT/ajaxrecipes/javascript/variablebehavior.html
    function GlobalScope() {
    info( "GlobalScope{scopedVariable}",  typeof( scopedVariable));
    scopedVariable = "globalscope";
    info( "GlobalScope{scopedVariable}",  "scopedVariable=" + scopedVariable +➥
 " type=" + typeof(scopedVariable));
 }
 function TestScope() {
 info( "OtherScope{scopedVariable}",  "scopedVariable=" + scopedVariable + " type="➥
 + typeof(scopedVariable));
 }

scopedVariable is defined in GlobalScope and referenced in TestScope. Since there is no var-based declaration of scopedVariable in GlobalScope, scopedVariable is put into the global scope. Running TestScope after GlobalScope will result in scopedVariable being defined globally, as shown in the following generated output:

    Info:GlobalScope{scopedVariable} undefined
    Info:GlobalToLocalScope{scopedVariable}  scopedVariable=globalscope type=string
 Info:TestScope{scopedVariable}  scopedVariable=globalscope type=string

In the generated output, GlobalScope is called, and at the beginning of the function implementation, scopedVariable is undefined. Then scopedVariable is assigned a buffer, and the generated output indicates that scopedVariable is not undefined and references a string. Calling TestScope illustrates that scopedVariable is global and is assigned a buffer. Now consider the same example, except a globally scoped variable is redeclared as a local variable using the var keyword.

    Source: /website/ROOT/ajaxrecipes/javascript/variablebehavior.html
    function AlwaysLocalScope() {
    info( "GlobalToLocalScope{scopedVariable}",  typeof( scopedVariable));
    scopedVariable = "AlwaysLocalScope";
    info(  "GlobalToLocalScope{scopedVariable}", "scopedVariable=" +  scopedVariable +➥
 " type=" + typeof(scopedVariable));
   var  scopedVariable;
   }

In the function implementation, scopedVariable is first assigned a buffer that does not use the var keyword. Thus, scopedVariable is declared at the global scope level. Or at least that is what you are led to believe. What happens is that the variable is declared at the local level because the last instruction of the function (in bold) declares the scopedVariable variable to be local. It may seem odd that a variable is declared to be local if somewhere in the function the var keyword is used. It gets even odder, in that if the var keyword is used in a decision block that is never executed, the variable is still declared local. To illustrate, first the AlwaysLocal function is called and then TestScope, which generates the following output:

    Info:AlwaysLocalScope{scopedVariable} undefined
    Info:AlwaysLocalScope{scopedVariable}  scopedVariable=AlwaysLocalScope type=string
 Warn:General error (scopedVariable is not  defined)

When the AlwaysLocalScope function is called, scopedVariable will be undefined, meaning it exists in neither global nor local scope. Then when the variable is assigned, the generated output will have a value and type. When the TestScope function is called, an exception is raised because scopedVariable is not defined. Now you know when a variable is declared in global scope and in local scope. The last test is to see what happens when a variable is declared in both global and local scope. The test involves calling the functions in the sequence: GlobalScope, TestScope, AlwaysLocalScope, and then TestScope. Calling this sequence generates the following output:

    Info:GlobalScope{scopedVariable} undefined
    Info:GlobalScope{scopedVariable}  scopedVariable=globalscope type=string
    Info:TestScope{scopedVariable}  scopedVariable=globalscope type=string
    Info:AlwaysLocalScope{scopedVariable} undefined
    Info:AlwaysLocalScope{scopedVariable}  scopedVariable=AlwaysLocalScope type=string
 Info:TestScope{scopedVariable}  scopedVariable=globalscope type=string

In the generated output, scopedVariable is declared and assigned in GlobalScope. The TestScope function verifies that scopedVariable exists. Then, when calling AlwaysLocalScope, var declares that any reference to scopedVariable within the function is a local variable reference. Thus, if there is a globally defined variable with the same name, it is not accessible within the scope of the function. You have two ways to reference a global variable: referencing via the window property or creating a function that is external to the executing function (meaning it’s not an inline function) and assigning the globally scoped variable. When a variable is not assigned, the typeof function returns undefined.

Once you assign a variable, typeof will return another value. If a variable is defined in the context of a function, then each and every time the function is called, the variable before being assigned will be undefined. At the global level, a variable can be unset by using the delete operator, as follows: delete scopedVariable; Usually, the delete operator is used to reset the property of an object. When delete is used with an identifier, a global variable reference is deleted. You cannot remove a reference to a function using delete. Let’s test another variation of scope using dynamic code. In JavaScript, using the eval function will execute a JavaScript buffer, which tests when a variable will be considered global scope and when it will be considered local scope. The AlwaysLocalScope function will thus be modified. For the first variation, AlwaysLocalScope will have a dynamic assignment:

    function AlwaysLocalScope() {
    info("AlwaysLocalScope{scopedVariable}",  typeof(scopedVariable));
    eval("scopedVariable  = 'AlwaysLocalScope'");
    info("AlwaysLocalScope{scopedVariable}",  "scopedVariable=" + scopedVariable +➥
 " type=" + typeof(scopedVariable));
 var scopedVariable;
 }

The modified code is shown in bold, and the assignment of scopedVariable is executed. Using eval in this manner has no effect, and the dynamic execution of the code is the same as if the code had not been modified. The advantage with eval is that you can assign a piece of code to a text buffer, and then execute that buffer. The scope of scopedVariable has not been changed because the var keyword still exists in the function declaration. The declaration when parsed by the JavaScript processor will result in a local variable declaration. One way to change the local declaration behavior is to embed the variable declaration in an eval statement, as shown in the following code modification:

    function AlwaysLocalScope() {
    info("AlwaysLocalScope{scopedVariable}",  typeof(scopedVariable));
    eval("scopedVariable  = 'AlwaysLocalScope'");
    info("AlwaysLocalScope{scopedVariable}",  "scopedVariable=" + scopedVariable +➥
 " type=" + typeof(scopedVariable));
   eval(  "var scopedVariable;");
 }

The modified code with respect to the original AlwaysLocalScope code is in bold. This time, both the assignment and the declaration of scopedVariable are dynamic, meaning that scopedVariable when assigned will be treated as a global variable. This is because when the first eval statement is executed, there is no declaration of scopedVariable, and the JavaScript runtime will store scopedVariable in the global space. To change the behavior and declare scopedVariable as a local variable, AlwaysLocalScope needs to be modified one more time, as follows:

    function AlwaysLocalScope() {
    info("AlwaysLocalScope{scopedVariable}",  typeof(scopedVariable));
    eval(  "var scopedVariable;");
    eval("scopedVariable  = 'AlwaysLocalScope'");
    info("AlwaysLocalScope{scopedVariable}",  "scopedVariable=" + scopedVariable +➥
 " type=" + typeof(scopedVariable));
 }

In the latest modification, the first eval is the declaration of scopedVariable using the var keyword. The first eval call results in the declaration of scopedVariable as a local variable. The second eval call assigns a value to scopedVariable, which is scoped as a local variable. When declaring variables in the context of functions or in global scope, keep the following points in mind:

• There are two scopes to a variable: local to a function and global.

• A local variable is declared using the var keyword, with the exception being the use of var in a global context. The use of var does not need to be at the beginning of a function.

• A global variable is declared when a variable is assigned without using the var keyword.

• It is good practice to declare variables at global level scope using the var keyword.

• Local and global variables with the same name do not overwrite each other. A locally declared variable hides a globally declared variable with the same name.

• When a variable is not declared, using typeof on the variable results in undefined.

• You can unset global variables using the delete operator.

• When using recursive functions, you should use locally declared variables.

• Recursion typically involves an initialization and an execution. Using JavaScript, the initialization and execution can be wrapped into a single function.

• Wrapping initialization and execution in a single function uses expectations, where the availability of variables is tested to determine a calling context.

• It is possible to use eval to dynamically declare local or global variables.

• Using eval causes the JavaScript processor to not perform a look-ahead when identifying local variables. Thus, to declare a local variable, the var keyword must be used before assigning a variable.

• Using the eval statement, a program could dynamically determine whether or not a variable should be declared at the local scope or the global scope.