before I begin the tutorial i'd just like to say that it is 100% MINE i am just transferring it from my old HF account.

Hello Everybody and welcome to the Java 'Advanced' tutorial!



Recursion


public void recurse(int i){
if (i==0)
        return;
System.out.print(i+" ");
recurse(i-1);
}

if the original call to recurse() is: recurse(10); then the program will print out the numbers 10-1 in reverse order with space between them: 10 9 8 7 6 5 4 3 2 1

When building a recursive method there are 3 main parts:

1)the parameters- what values need to be kept track of during my recursion? in the recurse() method above the value is just the number that needs to be printed
2)the checks- every recursive method must have a base case, that is a case in which the final solution has been found and recursion should stop. in recurse() that was when i=0. testing for the base cases are called the checks, because they check whether or not the method should do anything
3)the calls- for a method to be recursive, it must call itself. that's done in the calls section of the method. the calls run new methods with updated values . it is important to remember that any objects passed in these calls will change in the method from which they originated. so if you're going to be updating an object at any point, always send a copy of it in the recursive calls.(e.g. when sending an arraylist<string> called 'list' do not put 'list' in your parameters . sending something line 'new arraylist<string>list>; this constructor of the arraylist class creates a new arraylist with the same objects as the original)

public void recurse(int i /*the paramaters*/){
if (i==0)//the check -- have i found my stopping point?
         return;
System.out.print(i+" ");//what the method affects
recurse(i-1);//the call(s)
}

Binary recurssion

Definition- recursion in which 2 options are recursively tested. usually these options are:
1) pick an item
2) skit an item
another term for binary recursion that you might see is 'combinatorial optimization'

Example: The knapsack problem
a robber breaks into a house, and inside the house there is an assortment of items, each with a different value and weight. the robber can only carry a certain amount of items so what combination of items gets the robber the highest value while still allowing the robber to carry it?

Items:
Index: 0 1 2 3 4 5
values:9 4 5 4 2 10
weight:2 1 4 5 2 8
weight limit: 10

the highest valued combination here is the items at indexes: 0, 5 that gives us a value of 19. to figure this out we start at index 0m and recursively decide to both take the item at index 0 and skit the item at index 0. this process is repeated for the remaining indexes


ArrayList<Item> items = a list of items. each item has a value and weight
int bestval = 0;// the starting best value is 0.
int wieghtlimit = 10;// the robber can only hold up to a weight of 10.
void solveknapsack(int itemIndex, int currentValue, int currentWeight){
/*
*currentvalue and currentweight are the sums of values and weights,
*respectively of previous items.
*following the recursive method structure described earlier, the first
*thing to do is check for the base cases. the first base case
*is if the robber is carrying too much stuff
*/
if (currentweight > weightlimit) return;
 
//the next base case is if our current value is
//greater than the best value
 
if(currentvalue >bestval) bestval = currentcalue;
 
//that statement will ensure that our best solution is always saved.
//the final base case is if the item were trying to examine does not exist, that is, it is out //of bounds
 
if(itemindex>items.size()-1)return;
 
//the next step in out recursive structure is the calls
//the firs call assumes we take the current item:
solveknapsack(itemindex+1,currentvalue+itemindex.get(itemindex).VALUE,curentweig​​ht + items.get(itemindex).WEIGHT);
solveknapsack(itemindex_1,currentvalue,currentweight);
}

More coming soon! ( i just didnt want to bombard you guys)