# Get rid of recursion in fruit picker

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?

-
Instead of simply setting num to 31 or 71 or 91 or 1, you should choose a new random number. Otherwise you don't have equal random distribution. – Bergi Jun 10 '14 at 11:10
A sidenote: in the posted code, grapes is never decremented, and when all fruits are depleted, only grapes are added. If grapes is decremented however, you'd get infinite recursion (or stackoverflow) because there's no escape if all fruits are 0. – Me.Name Jun 10 '14 at 11:19
Generate sorted array and shuffle it. Will be O(n) and fully iterative. And BTW if you want to know if a code is fast enough for your needs benchmark it. Noone knows your requirements better than you do. – Yury Tarabanko Jun 10 '14 at 11:49
I had an answer for your question, which I have now deleted because it missed the core issue in your code, but it raises another question: what should the behaviour be as you 'deplete' the available inventory of fruit? Do the odds of the 'next' fruit change as you go, or are the odds constant, and you just re-select until you get something? – rolfl Jun 10 '14 at 18:11
That system is the system I answered here, but your use-case, you have 10 fruit, and you select 10 fruit, there is no reason to have anything random... it's just the order that's changing. – rolfl Jun 10 '14 at 21:32

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

-
+1 for the refactoring and getting away from the nested ifs. – Dylan Cristy Jun 10 '14 at 21:40

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--;
}
if (num < 70 && kiwi > 0) {
fruit.push("kiwi");
kiwi--;
}
if (num < 90 && banana > 0) {
fruit.push("banana");
banana--;
}
if (grapes > 0) {
fruit.push("grapes");
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.

-
Definitely best answer. I think it's worth mentioning that your loop condition will never actually evaluate to false, because you return when loop count is 1 anyway. – Cruncher Jun 10 '14 at 16:06
@Cruncher, you are right. I really like returning the "no fruit left" part, I could do away with that, but I think it is necessary for a function to let you know when it hasn't done what you expect it to do. – Malachi Jun 10 '14 at 16:25
The loop count can be replaced with a simple boolean even. Not sure if that would be more or less readable. – Cruncher Jun 10 '14 at 16:46
I had it set up differently with a boolean, but I think you are right, before I had a boolean but no while loop. now it would work I think. but it would still behave the same way. but it would be cleaner – Malachi Jun 10 '14 at 16:51
Oh. This has a bug actually. Consider num < 30 when apples = 0 and grapes = 0. You'll get "no fruit left". If there are grapes, it will add grapes without checking kiwis or bananas – Cruncher Jun 10 '14 at 17:18

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.

-
How does the loop end ? – Marc-Andre Jun 10 '14 at 13:36
@Marc-Andre, break statements, where in recursion the functions is not called. – micnic Jun 10 '14 at 13:38
that is pretty code, almost too pretty for JavaScript. LOL – Malachi Jun 10 '14 at 14:56
It should be noted that the second solution, although much neater than the OP's code, has essentially an identical execution path. It is recursion for all intents and purposes. – Cruncher Jun 10 '14 at 16:00

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.

-
Indeed, the array literal is faster, especially on Chrome (not that it makes any difference when creating just one array). On the other hand, new Array(10) could be beneficial, as it pre-allocates an array of the right size. But new Array() was never in the code to begin with, so I don't know why you're mentioning it. – 200_success Jun 10 '14 at 20:24
Please elaborate on "'grapes' will get wrongly populated sometimes"? – 200_success Jun 10 '14 at 20:26
It is certainly possible to have poorly performing recursive code, even if it never touches the DOM. Could you qualify your statement a bit? – 200_success Jun 10 '14 at 20:27
I have tested this snippet and sometimes no. of grapes are different obviously because of random function. Regarding poorly performing recursive code, its up to developer where he/she need to go in and come out of recursion. Modifications in DOM while big recursion gives a performance hit as the elements has to be searched in whole DOM again and then updated. Refer recursive sorting algorithms en.wikipedia.org/wiki/Sorting_algorithm – Hemant Barhate Jun 11 '14 at 14:21

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

-

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.

-
You saved me the need for recursion – stackunderflow Jun 10 '14 at 12:59