Would someone be kind enough to explain this program (taken from a book tutorial) step by step in plain language to help me understand recursion?
var reverseArray = function(x,indx,str) {
return indx == 0 ? str : reverseArray(x, --indx, (str+= " " + x[indx]));;
}
var arr = new Array('apple', 'orange', 'peach', 'lime');
var str = reverseArray(arr,arr.length,"");
alert(str);
var arr2 = ['car','boat','sun','computer'];
str = reverseArray(arr2,arr2.length."");
alert(str);
Sure, but it's probably easier to read written like this:
var reverseArray = function(x,indx,str) {
if (indx === 0) { // Termination condition
return str; // return default
} else {
return reverseArray(x, --indx, str + " " + x[indx]); // recur on x, reduce indx, update default
}
}
Recursion is just a function calling itself, right? The important thing is the termination condition that prevents the function from calling itself forever. In this case that's this line:
if (indx === 0)…
As long as indx is not 0, the function will continue to call itself with updated arguments. The subsequent call does the same thing, but the final product str contains the value passed from the parent call to reverseArray. Eventually indx reaches zero and the value of str is the combined value passed down from parent to child. That is what is returned by the line:
return str; // ' lime peach orange apple'
It gets returned to its parent, and its parent returns that to its parent and so on until the top-most frame is reached.
arr = new Array('apple', 'orange', 'peach', 'lime');
reverseArray(arr,arr.length,""); // ['apple', 'orange', 'peach', 'lime'], 4, ""
+['apple', 'orange', 'peach', 'lime'], 3, "" + " " + x[3] = " lime";
++['apple', 'orange', 'peach', 'lime'], 2, " lime" + " " + x[2] = " lime peach";
+++['apple', 'orange', 'peach', 'lime'], 1, " lime peach" + " " + x[1] = " lime peach orange";
++++['apple', 'orange', 'peach', 'lime'], 0, " lime peach orange" + " " + x[0] = " lime peach orange apple"; // indx == 0, so this string returns
== in the termination condition to type-strict. So I changed it now.Would the following suffice?
// declare a variable which is to be the function for reversing the array
var reverseArray = function(x,indx,str) {
// check if the index has reached zero. if it did, return the concatenated string,
// else concatenate the string with the next item in the array at the current index.
// for each subsequent call to the function, the index is decreased by one, working
// the array backwards.
return indx == 0 ? str : reverseArray(x, --indx, (str+= " " + x[indx]));;
}
// declare an array of fruit
var arr = new Array('apple', 'orange', 'peach', 'lime');
// declare a variable and assign it's value to the result of the recursive function,
// sending through the fruit array, the amount of items in it and an empty string as
// parameters to the function.
var str = reverseArray(arr,arr.length,"");
// show a dialogue box with the result of the function
alert(str);
// do the same as in the fruit example...
var arr2 = ['car','boat','sun','computer'];
str = reverseArray(arr2,arr2.length."");
alert(str);
One of the easiest ways to look at it is, think of it as calling another function having the same logic. Each function calls another function until a termination condition is met, in this case indx==0. At that point, it stops calling another function and returns str.
for eachis only available in Firefox afaik. Andfor...inshould not be used to iterate over an array. I know thatlengthdoes not hold the actual size of the array. But it seems there is no 100% reliable way to iterate an array.