JavaScript Recursion

Question

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);

• Bob: By the way, I'd recommend 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
• kojiro: Besides, nobody uses recursion to reverse an array except for academic questions. ;)
• Felix Kling: @Bob: How would you iterate over the array?
• Bob: @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
• Felix Kling: @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.

Answer 1

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

• mjmitche: thank you, can you please explain in more detail what you mean when you say "recur on x" and "update default"
• mjmitche: it would also be nice if you could explain "return to its parent" by reference to the code/problem. thank you.
• kojiro: Looking back at this, I can't remember why I didn't change the == in the termination condition to type-strict. So I changed it now.

Answer 2

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);

• mjmitche: Thank you very much. Can you please explain in more detail the significance of the parameter "" in (arr, arr.length, "").
• FarligOpptreden: The "" is just a blank string, i.e. nothing, being passed through, so that the string can start being concatenated from nothing. In that instance, it will be concatenated as follows: "", "lime", "lime peach", "lime peach orange", "lime peach orange apple"
• mjmitche: could you also please explain the following: x[indx]
• FarligOpptreden: x refers to the array, while indx is the INDEX that you're accessing in the array. In other words, you want to get the item at "indx" in the array "x".
• mjmitche: one more thing if you don`t mind. why does this example use two arrays i.e. arr and arr2. Is that somehow important to understand recursion? much appreciated.

Answer 3

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.