JavaScript recursion
Would someone be kind enough to explain this program (taken from the tutorial) step by step in simple 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);
source to share
Is the following enough?
// 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 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);
source to share
Sure, but it's probably easier to read 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 being called forever. In this case, this line:
if (indx === 0)…
As long as indx is not 0, the function will continue to call itself with updated arguments. The next call does the same, but the final product str
contains the value passed from the parent call to reverseArray
. Eventually indx reaches zero and the str value is the combined value passed from parent to child. This is what is returned by the line:
return str; // ' lime peach orange apple'
It returns to its parent, and its parent returns it to its parent, and so on, until the topmost 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
source to share
One of the easiest ways to look at this is to think of it as calling another function that has the same logic. Each function calls a different function until the termination condition is met, in which case indx == 0. At that point, it stops calling another function and returns str.
source to share