JAVASCRIPT- Implementing a Recursive Algorithm

Implementing a Recursive Algorithm

Problem

You want to implement a function that will recursively traverse an array and return a string of the array element values, in reverse order.

Solution

Use a function literal recursively until the end goal is met:

var reverseArray = function(x,indx,str) {
 return indx == 0 ? str :
 reverseArray(x,--indx,(str+= " " + x[indx]));
}
var arr = ['apple','orange','peach','lime'];
var str = reverseArray(arr,arr.length,"");
console.log(str);
var arr2 = ['car','boat','sun','computer'];
str = reverseArray(arr2,arr2.length,"");
console.log(str);

Before looking at the solution, I want to cover the concept of recursion first, and then look at functional recursion.Recursion is a well-known concept in the field of mathematics, as well as computer science. An example of recursion in mathematics is the Fibonacci Sequence:

f(n)= f(n-1) + f(n-2),
 for n= 2,3,4,...,n and
 f(0) = 0 and f(1) = 1

A Fibonacci number is the sum of the two previous Fibonacci numbers. Another example of mathematical recursion is a factorial, usually denoted with an ex‐ clamation point (4!). A factorial is the product of all integers from 1 to a given number n. If n is 4, then the factorial (4!) would be:

4! = 4 x 3 x 2 x 1 = 24

These recursions can be coded in JavaScript using a series of loops and conditions, but they can also be coded using functional recursion. A common example of JavaScript recursion is the solution for a Fibonacci:

var fibonacci = function (n) {
 return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

or a factorial:

function factorial(n) {
 return n == 1 ? 1 : n * Factorial(n -1);
}

In the Fibonacci example, n is tested to see if it is less than 2. If it is, it’s returned; otherwise the Fibonacci function is called again with (n – 1) and with (n – 2), and the sum of both is returned. A little convoluted? The second example with the factorial might be clearer. In this example, when the function is first called, the value passed as argument is compared to the number 1. If n is less than or equal to 1, the function terminates, returning 1.

However, if n is greater than 1, what’s returned is the value of n times a call to the factorial function again, this time passing in a value of n – 1. The value of n, then, decreases with each iteration of the function, until the terminating condition (or base) is reached. What happens is that the interim values of the function call are pushed onto a stack in memory and kept until the termination condition is met. Then the values are popped from memory and returned, in a state similar to the following:

return 1;
return 1;
return 1 * 2;
return 1 * 2 * 3;
return 1 * 2 * 3 * 4;

In the solution, we reverse the array elements by using a recursive function literal. In‐ stead of beginning at index zero, we begin the array from the end length, and decrement this value with each iteration. When the value is zero, we return the string. If we want the reverse—to concatenate the array elements, in order, to a string—modify the function

var orderArray = function(x,indx,str) {
 return indx == x.length-1 ? str : orderArray(x,++indx,(str+=x[indx] + " "));
}
var arr = ['apple','orange','peach','lime'];
var str = orderArray(arr,-1,"");
// apple orange peach lime
console.log(str);

Rather than the length of the array, we start with an index value of –1, and continue the loop until one less than the length of the array. We increment the index value rather than decrement it with each loop. Most recursive functions can be replaced with code that performs the same function linearly, via some kind of loop. The advantage of recursion is that recursive functions can be fast and efficient. In addition, it adheres to the functional programming para‐ digm, which means the code is going to be more reliable and consistent. The downside, though, is that recursive functions can be very memory-intensive. How‐ ever, the next section explains why this is likely to change in future implementations of JavaScript.

Tail Call Optimization

Promised in ECMAScript 6 is a new JavaScript feature called tail call optimization, or more properly, proper tail calls. In the following recursive factorial function (less cryptically displayed than the one I provided previously):

function factorial(num)
{
 if (num == 0) {
 return 1;
 }
 // Otherwise, call this recursive procedure again.
 else {
 return (num * factorial(num - 1));
 }
}

The call to the function at the end of the function is the tail call. Currently, each time the recursive function is called, another frame is added to the call stack. Basically what’s happening is the JavaScript engine is keeping track of the function call and the data passed to it. Enough calls, and the memory is exhausted and you get a RangeError. What the proper tail call (optimization) does is reuse the same frame rather than add a new one. Once this feature is incorporated, the possibility of a RangeError error hap‐ pening is eliminated.