Variables and Recursive Functions

You probably noticed the use of local variables in the previous Fibonacci recursive function. You should regularly use local variables in recursive functions. Make this a habit so you never forget, because it is laborious to detect variable scope-related problems, even when you know the function does not work correctly. This is where variable tracing tables come in handy. Here is the preceding script with the keyword var absent:

text = "place\t\ts1\t\ts2\t\tval\r"
text += "==================================\r"

function getVal(place) {
  if (place == 1 || place == 2)
 return 1
  s1 = getVal(place – 2)
  s2 = getVal(place – 1)
  text += place + "\t ||  \t" + s1 + "\t  ||  \t"
  text += s2 + "\t  ||  \t" + (s1 + s2) + "\r"
  return s1 + s2
}

getVal(6)

alert(text)

As you could expect, the table’s content differs:

An obvious error appears on the sixth line, when the function is called with the value 5. The function returns 4 instead of 5. The seventh line (where place is 6) also reflects an error. The function should return 8, not 5. The first mistake encountered appears to be when the function is invoked with the argument 5. The problem there is the variable s1, because it holds an incorrect value. The recursive algorithm seems to be fine, so the only possible mistake is with the variables. The exact problem is that the variables are global, not local.

Focus on the call to the function, with the value 5. That function then calls itself with the value 3, and after a few more recursive calls, the correct value is returned to s1. Remember that this variable is global. The first function execution (with 5) now calls itself again, this time with the value 4. A few more recursive calls take place, during which the values of s1 and s2 are modified. s1, like s2, is global, so its value is not the same value that was assigned to it in the initial execution of the function (with the argument 5). It holds a value assigned to it by a deeper function call, which is obviously incorrect for the current function. The wrong value of s1 at this point influences the result. The same problem applies to all function calls with a value greater than 4.

If you do not understand the cause of the problem, use the following script:

var text = ""

function getVal(place) {
  if (place == 1 || place == 2)
 return 1
  s1 = getVal(place – 2)

  var tempS1 = s1 // assign correct s1 value to tempS1

  s2 = getVal(place – 1)
// check if s1 was modified by the preceding statement
  if (tempS1 != s1) {
text += ">>>\tThere appears to be an error in the "
text += "current execution of the function (place = "
text += place + ") --\rthe value of s1 has unexpectedly"
text += " been modified (" + tempS1 + " => " + s1 + ")\r"
  }
  return s1 + s2
}

getVal(6)

alert(text)

The following message explains it all:

Summary

In this chapter we focused on advanced function techniques and variable scope. Failing to pay attention to the variable scope concept results in hours of frustrating work trying to find bugs in simple scripts. After attaining a deeper understanding of variables and their scope, you will find it easy to write scripts with many functions, interleaving local and global variables. This chapter also presented some important matters related to parameters, such as referring to a variable number of arguments. Scripting specially designed dialog boxes took advantage of this feature. Another important concept discussed in the chapter is recursion. We found out how to debug recursive algorithms with a formatted table to trace variables.