Notice that the else statement is commented because it is not necessary.

The fact() function satisfies two rules. First, it has an ending point. Second, it simplifies the problem because fact(num – 1) is simpler than fact(num). Recursive functions should always follow these two rules.

Figure 9-8.  A formatted table that helps a scripter trace variables throughout a recursive execution.

Recursive functions have a few advantages:

• Invariably, recursive functions are clearer, simpler, shorter, and easier to understand than their nonrecursive counterparts.
• The program directly reflects the abstract solution strategy (algorithm). The recursive factorial function, for example, uses the common mathematical strategy to solve the problem.

At first, it may seem that recursive functions are more difficult, but they become easier with practice.

Recursion can also be used to compute a value in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, ...). The basic algorithm is:

getVal(1) = 1
getVal(2) = 1
getVal(place) = getVal(place – 1) + getVal(place – 2)

Here is a JavaScript function to calculate the value of the sequence in the specified place:

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

A call to this function could be:

var fibValue7 = getVal(7) // fibValue7 = 13

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

1, 2, 3, 4, 5, 6, 7, 8, 9, ...

---

Note:  The bottom row specifies the place; the top row specifies the Fibonacci value at that space.

---

Figure 9-9.  A table that helps the scripter detect variable's scope-related problems.

Notice that we once again left out the unnecessary else statement.

Some programmers prefer not to use complex expressions and values returned by other functions with the return statement. Instead, they assign those values to variables and then return them:

function getVal(place) {
  if (place == 1 || place == 2)
 return 1
  var s1 = getVal(place – 2)
  var s2 = getVal(place – 1)
  return s1 + s2
}

Tracing Values in Recursive Functions

Sophisticated recursion algorithms are often difficult to follow. Many values change, some in the way you expect, while others make surprising “moves.” JavaScript still does not have a decent debugger to help us with that, so we must develop our own tools, using output statements to evaluate expressions and variables. With a few additional statements, it is possible to display the values of the variables and parameters throughout the recursive execution. Here is the getVal() function with a few additions to track values during the recursion:

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

function getVal(place) {
  if (place == 1 || place == 2)
 return 1
  var s1 = getVal(place – 2)
  var 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)

Note that it is legal not to use the value returned by a function (getVal(6) in this case). In the preceding script segment a global variable (text) is used to store the formatted tracing of the execution course. A self-formatted table is created and displayed in an alert box after the execution terminates. The following values are put in each row of the table:

• The value of the parameter (place) in the current function call. The assignment to text is done at the end of the function (after the recursive calls to the function), so the first function in the table is the last to be called.

  
  Figure 9-10.  A dialog box that displays a list of errors tracked during the recursive execution.

• The values of s1, s2, and their sum

The exact output of the preceding script segment (the argument handed over to the function is 6) is:

From here it is effortless to track all the function calls and the values of the variables during the recursion.

Use recursive algorithms carefully. Do not create functions that call themselves hundreds of times if there is a simple nonrecursive alternative. If you doubt this caution, try crashing your browser or computer by calculating the 100th value of the Fibonacci sequence!