]
02-13-2013, 12:25 AM
In this thread I will be going over some very advanced stuff, if you do not know java that well please go check my java-the bare basics tutorial or any of my other tutorials.
Recursion
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)
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
Recursion
Hidden Content
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)
Hidden Content
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
Hidden Content