programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Recursion

Todd Rushing
Greenhorn
Posts: 4
I am trying to make a program that will take a given weight for a backpack as user input, and will go through a random array of five numbers to find the combination that will add up to the user's given weight. I think i have a general idea of how this would work, but i would like to use recursion for this problem. I am kinda lost now, so any and all help is appreciated.

James Carman
Ranch Hand
Posts: 580
What do you have so far?

Todd Rushing
Greenhorn
Posts: 4
Well, i only have ideas of the combination i can use to solve for which weights will add up to the defined weight, other than that, there is no code.

Henry Wong
author
Sheriff
Posts: 23295
125
Originally posted by Todd Rushing:
I am trying to make a program that will take a given weight for a backpack as user input, and will go through a random array of five numbers to find the combination that will add up to the user's given weight. I think i have a general idea of how this would work, but i would like to use recursion for this problem. I am kinda lost now, so any and all help is appreciated.

Recursion is a technique just like any other. You don't use it because you "like to use" it for a problem. Either it fits with your "general idea" or it doesn't.

Henry

Todd Rushing
Greenhorn
Posts: 4
im pretty sure i can figure out how its done using a loop, but i was wondering if it is possible with recursion, and how that is done

Todd Rushing
Greenhorn
Posts: 4
Here's what ive got so far, but obviously i am not to good with grasping the concept of recursion at al, i think i need to completely start over

import javax.swing.JOptionPane;
import java.util.Random;
public class backpack{

int itemCount;
int maxWeight;

public static void main(String[] args){
int[] packItems = new int[5];
double x;
int n;

Random myRandom = new Random();

// make the array!
for (int i = 0; i < 5; i++) {
packItems[i] = 0;
}

for (long i=0; i < 20; i++) {
// generate a new random number between 0 and 9
x = myRandom.nextDouble() * 10.0;
n = (int) x;

packItems[n]++;
}

public int testWeight(){
if((packItems[itemCount]+packItems[itemCount-1]+packItems[itemCount+1]) == 20){
System.out.println("The Combination is:" + packItems[itemCount]);
}
else
{
itemCount ++;
return testWeight();
}
}
}
}

Henry Wong
author
Sheriff
Posts: 23295
125
It looks like you are just taking a looping algorithm, and forcing it to be recursive. And ...

I don't think the looping algorithm works. What if the solution requires items that are not next to each other to be packed.

Henry

Ryan McGuire
Ranch Hand
Posts: 1143
9
I think I understand what you're trying to do.

Try making method (rather than trying to make main() recursive) that takes the current stat of the backpack and the number of items left to do. This method would pack one item and then call itself with the number of items yet to go decremented by one. Use the return code to signify whether the packing has been sucessfully completed. And use the return at each level to determine whether or not to try another random number.

It obviously still needs some details worked out, but there are the basics.

Ryan

M Beck
Ranch Hand
Posts: 323
in theory, recursion is more general than iteration — that is, anything you can do with an iterative loop, you can also do with a recursive function. (provided you can figure out how to write it, of course, and provided it doesn't recurse too deeply for your language's stack.)

then again, in theory "call/cc" is the most general control structure around, but personally i'm just as happy having if/then/else and switch to use instead...

[edit: corrected thinko.]
[ May 14, 2005: Message edited by: M Beck ]