|
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. Recursive functions have a few advantages:
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, ...
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 FunctionsSophisticated 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 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!
|
|||||||||||||||||||||||
With any suggestions or questions please feel free to contact us |