Get rid of recursion in fruit picker

Question

I have this simple code and it is working fine it is self explanatory: the user will choose a random number 10 times and based on the random number the array will be filled by fruits.

var fruit =[];

for( x=0; x<10,x++){
    var r = Math.floor(Math.random() * 100 + 1);
    choose(r);
}


function choose(num){

  if(num <30){

      fruit.push("apple");

   }else if(num <70){
   fruit.push("kiwi");

    }else if(num< 90){

    fruit.push("banana");

    }else{

    fruit.push("grapes");
};

}

However in the code above, requirement is not restrictive; so below the number of available fruit is limited, and even if the random number choose a fruit, i have first to check if it is available in store or not. if the fruit is not available I should fall through to the next available fruit. The code below is working fine; but I had to do it via recursion in case fruit is not available.

var apple = 2;
var kiwi = 1;
var banana = 5;
var grapes = 2;


var fruit =[];

for( x=0; x<10,x++){
    var r = Math.floor(Math.random() * 100 + 1);
    choose(r);
}


function choose(num){

  if(num <30){
     if(apple>0){
     fruit.push("apple");
     apple--;
     }else{
     num = 31;
     choose(num);
     };

  }else if(num <70){

      if(kiwi>0){
         fruit.push("kiwi");
         kiwi--;
         }else{
        num = 71;
        choose(num);
        };

  }else if(num< 90){
       if(banana>0){
         fruit.push("banana");
         banana--;
        }else{
          num = 91;
          choose(num);
        };
}else{
      if(grapes>0){
        fruit.push("grapes");
        grapes--;
      }else{
         num = 1;
         choose(num);
      };
};

}

This code is working and my question is:

Since this selection of food is happening many times in the page, and it involves recursion, I am worried that this will degrade the performance.

Is there any advice in this regard? or any change suggested to the code or algorithm?

Answer 1

Problems

• for( x=0; x<10,x++){

  The comma should be a semicolon.

  You should be in the habit of declaring your variables with var (even though it makes no difference in this case, since x is in the global scope).

  x has a connotation of being a floating-point number. A dummy variable for a loop is typically named i.

• Your probabilities may be slightly skewed.

  var r = Math.floor(Math.random() * 100 + 1) sets r to be an integer from 1 to 100, inclusive. When you test for if(num <30), that gives a 29% probability of wanting "apple". The probability of wanting "grapes" is 11%. I assume you intended the probabilities to be apple: 30%, kiwi: 10%, banana: 50%, and grapes: 10%.

Simplification

A simpler way to implement fallbacks is to eliminate both the recursive choose(num) calls and the elses.

function choose(num){

  if(num <30){
     if(apple>0){
     fruit.push("apple");
     apple--;
     }else{
     num = 31;
     };

  }
  if(num <70){

      if(kiwi>0){
         fruit.push("kiwi");
         kiwi--;
         }else{
        num = 71;
        };

  }
  if(num< 90){
       …

However, that function still has some severe problems…

Expressiveness

The code is hard to maintain, because information is spread out all over the place.

• You have four variables and four if branches for four kinds of fruits.
• The names of the fruits are stored in the fruit.push(…) statements.
• The probabilities for each fruit are encoded in the if (num < …) conditions as well as the fallback code.
• The code for handling each condition is largely copy-and-paste.

If you ever need to add a fruit, change the kinds of fruits available, or change the fruit preferences, it will be a pain.

Rather, it would be better to consolidate all the information about the fruits in one array. The code should implement the logic that you described in your question, without hard-coding any information about the specific fruits.

var stock = [
    {
        name: 'apple',
        cumulativeProbability: 0.30,
        available: 2,
    },
    {
        name: 'kiwi',
        cumulativeProbability: 0.40,
        available: 1,
    },
    {
        name: 'banana',
        cumulativeProbability: 0.90,
        available: 5,
    },
    {   //   ♪    ♪   ♪  ♩    ♫  ♩    ♫   
        // "Yes, we have no bananas today!"
        name: 'grapes',
        cumulativeProbability: 1.00,
        available: 2,
    },
];


function browse(stock) {
    while (true) {
        var r = Math.random();
        var disappointed = false;
        for (var i = 0; i < stock.length; i++) {
            var item = stock[i];
            if (disappointed || r < item.cumulativeProbability) {
                if (item.available) {
                    return item;
                } else {
                    disappointed = true;
                }
            }
        }

        // Out of stock of desired fruit and fallbacks
        var inventory = stock.reduce(function(sum, item) {
            return sum + item.available;
        }, 0);
        if (!inventory) {
            // There is no stock of ANY item.  Break to prevent
            // infinite loop.
            break;
        }
    }
}

function pick(item) {
    if (item) {
        item.available--;
        return item.name;
    }
}

var fruit = [];

for (var i = 0; i < 10; i++) {
    fruit.push(pick(browse(stock)));
}

Answer 2

Micnic was almost there, but I think that you can lose the recursion completely by separating your if statement into several if statements

function choose(num){
    var looped = false;
    while (!looped) {
        if (num < 30 && apple > 0) {
            fruit.push("apple");
            apple--;
            return "added apple";    
        }
        if (num < 70 && kiwi > 0) {
            fruit.push("kiwi");
            kiwi--;
            return "added kiwi";
        }
        if (num < 90 && banana > 0) {
            fruit.push("banana");
            banana--;
            return "added banana";
        }
        if (grapes > 0) {
            fruit.push("grapes");
            grapes--;
            return "added grapes";
        } else {
            if (looped) {
                return "no fruit left";
            }
            num = 1;
            looped = true;
        }
    }
};

This will remove the recursion (sounds like that is what you want to do) and will still cascade through the fruit. notice that if the number is 95 and there are no grapes it will still recursively call the choose function with a number of 1 to cover the rest of the fruit, The only difference here is that you don't have the recursive call in every if statement, and you have less than half of the if statement calls. I also made sure that the this wouldn't loop more than once by implementing a while loop that will only ever loop once.

If the number is 40 it will start at checking for kiwi's if there are none then then it will check for bananas.

I think this is exactly what you were looking for.

I don't like a function returning undefined, so I added the return "added {fruit}"; but you could just have return; if that is your preference.

Answer 3

From my experience I would say that recursion in JavaScript is a bad practice, it influence a lot the performance, I'd recommend to use recursion only for code where the performance is not critical. In your case I propose to make this change:

function choose(num) {
    while (true) {
        if (num < 30) {
            if (apple > 0) {
                fruit.push('apple');
                apple--;
                break;
            } else {
                num = 31;
            }
        } else if (num < 70) {
            if (kiwi > 0) {
                fruit.push('kiwi');
                kiwi--;
                break;
            } else {
                num = 71;
            }
        } else if(num < 90) {
            if (banana > 0) {
                fruit.push('banana');
                banana--;
                break;
            } else {
                num = 91;
            }
        } else {
            if (grapes > 0) {
                fruit.push('grapes');
                grapes--;
                break;
            } else {
                num = 1;
            }
        }
    }
}

or, a better solution in my opinion :

function choose(num) {

    function chooseApple() {
        if (apple > 0) {
            fruit.push('apple');
            apple--;
        } else {
            chooseKiwi();
        }
    }

    function chooseKiwi() {
        if (kiwi > 0) {
            fruit.push('kiwi');
            kiwi--;
        } else {
            chooseBanana()
        }
    }

    function chooseBanana() {
        if (banana > 0) {
            fruit.push('banana');
            banana--;
        } else {
            chooseGrapes();
        }
    }

    function chooseGrapes() {
        if (grapes > 0) {
            fruit.push('grapes');
            grapes--;
        } else {
            chooseApple();
        }
    }

    if (num < 30) {
        chooseApple();
    } else if (num < 70) {
        chooseKiwi();
    } else if(num < 90) {
        chooseBanana();
    } else {
        chooseGrapes();
    }
}

Note: No need to add semicolon after if-else statements.

Answer 4

As long as you re not accessing DOM element in javascript recursion, you will not face serious performance issue.

By your current logic and random number generation, 'grapes' will get wrongly populated sometimes.

var fruit = []; is better than var fruit = new Array(); for performance.

Answer 5

http://en.wikipedia.org/wiki/Tail_recursion

It is possible that recursion will be more expensive, depending on if the recursive function is tail recursive (last line is recursive call). Tail recursion should be recognized by the compiler and optimized to its iterative counterpart (while maintaining the concise, clear implementation you have in your code).

I would write the algorithm in the way that makes the most sense and is the most clear for the poor sucker (be it yourself or someone else) that has to maintain the code in a few months or years. If you run into performance issues, then profile your code, and then and only then look into optimizing by moving over to an iterative implementation. You may want to look into memoization and dynamic programming.

http://en.wikipedia.org/wiki/Memoization

http://en.wikipedia.org/wiki/Dynamic_programming

Answer 6

Regarding:

or any change suggested to the code or algorithm?

In the current setup, recursion could be avoided by using a while loop instead of recursion and breaking if found, but that wouldn't do much good for readability. Just my preference, but I'd put the amounts and information such as the threshold and name in objects and loop through them. That way the object definitions can be put separately from the selection and code redundancy is prevented. e.g.:

var fruit =[] ,
  fruitstore = [
  {Name : "apple", Amt : 2, Th : 30},
  {Name : "kiwi", Amt : 1, Th : 70},
  {Name : "banana", Amt : 5, Th: 90},
  {Name : "grapes", Amt : 2, Th: 101}
  ];

function choose(num){
    for(var j= 0; j < 2 ; j++){ 
    for(var i = 0; i < fruitstore.length; i++){
       var fr = fruitstore[i];
       if(num < fr.Th && fr.Amt > 0){
          fruit.push(fr.Name); 
          fr.Amt--;
          return; //you could also choose to remove the fruit from the fruitstore
       }
    }  
    //can only be reached if grapes in store = 0, used a while (true) loop, but you could use recursion, only for this scenario
    num = 1;     
   }
}

for( x=0; x< 10;x++){
    var r = Math.floor(Math.random() * 100 + 1);
    choose(r);
}

This emulates the current code. It could be altered to do something like return another random fruit if the found item amount is 0. The code itself isn't optimized, but by having the information in objects, the chosen approach can quickly be changed and new fruits can be added without having to alter the function.