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','puter'];
str = reverseArray(arr2,arr2.length."");
alert(str);

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','puter'];
str = reverseArray(arr2,arr2.length."");
alert(str);

• javascript
• recursion

• 1 By the way, I'd remend never using this to reverse a JavaScript array. It's perfectly valid to say something like this: arr[4000000] = 0, which will set the length of the array to 4 million, which will mean this will call the function 4 million times and crash the browser :P – Bob Commented Mar 2, 2011 at 6:50
• Besides, nobody uses recursion to reverse an array except for academic questions. ;) – kojiro Commented Mar 2, 2011 at 6:54
• @Bob: How would you iterate over the array? – Felix Kling Commented Mar 2, 2011 at 6:57
• @Felix I'd probably use a for-each loop if the content size isn't known. With the way arrays are stored in JavaScript, the length isn't necessarily how many variables are actually in the array. With a for-each loop it would only iterate over members that actually exist. Of course, if you know the size then a for-loop, or this recursion method would work – Bob Commented Mar 2, 2011 at 16:08
• 1 @Bob: for each is only available in Firefox afaik. And for...in should not be used to iterate over an array. I know that length does not hold the actual size of the array. But it seems there is no 100% reliable way to iterate an array. – Felix Kling Commented Mar 2, 2011 at 16:17

3 Answers 3

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 bined 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

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','puter'];
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.