1.What is Recursion?
Recursion is a method that calls itself. Normally I find recursion useful for solving issues of an unknown size, or something that might just take many nested loops. One example is for creating a “tree” program in a language, that transverses a drive, and reports what files are in each folder. Because folders have sub folders which all have differing amounts of files, using a loop as opposed to recursion would make life a lot harder.
One important part of recursion is the base case, which stops the recursive method from going on to infinity and causing a stack overflow error.
Stack def. http://en.wikipedia....data_structure)
Here is a simple example of recursion
private int triangles(int rows)
{
if(rows == 0) //Base Case
return 0;
return rows + triangles(--rows); //Recursive call
}
if that code was called by
int totalRows = triangles(5);
the yielded amount would end up being 15. Lets go through how that works out!
The method is called
rows isnt equal to zero so the method isnt over
step 1. 5 + triangles(4)
which then performs the same thing(Red indicates the code that is added is this step)
step 2. 5 + 4 + triangles(3)
step 3. 5 + 4 + 3 + triangles(2)
step 4. 5 + 4 + 3 + 2 + triangles(1)
step 5. 5 + 4 + 3 + 2 + 1 + triangles(0)
step 6. The base case is hit on this run through and thus the total is added up, so the program returns,
5+4+3+2+1+0 = 15
2.Data gathered
The following tests were performed using iterations of 3000
Although averages were not gathered for any other data, tests of iterations on 30 were performed to see if the amount of iterations in one run affected the results(in terms of differences, the speeds were lower, because less iterations), they were not different
Due to the amount of data, outliers were NOT thrown out
This was test was performed on two different machines, XP x86, and Windows 7 x64
Times were Taken using the java.lang.System.nanoTime() method
The only loop that was tested was a for loop
Between the recursion start and end time, an if statement was ran during each iteration, which could have impacted recursions scores negativity, although unknown in impact, it is assumed to have made little difference
The following graphs were created by taking the averages of 100 interations through x interations(3000 in graph, also 30 not in graph), averaging those, doing that y number of times, doing that 5 times, then averaging all those totals(5 totals showed under Totals)
Total Interations(x6 because 3 tests for loops, and 3 test for recursion): ((100*USER_DEFINED_INTER)*USER_DEFINED_NUM_TESTS)*USER_DEFINED_NUM_FILES
so after deciding that I should write an article, I decided to determine when recursion passed a loop in terms of efficiency.
The efficiency of loops and recursion were determined using three algorithms of increasing difficulty in terms of processing power required to solve them.
The Following will refer to the difficulty of the algorithms based on a scale 1-5, 1 being the easiest, while 5 being hardest.
Level 1. a simple loop/recursive method that increments a variable by 1
Level 2. (double)(((int)(i * Math.sqrt(i*i - 4*i*i)) & 0xA)<<2)
Level 3. Math.pow(Math.sqrt(Math.sqrt(Math.pow(i/5, Math.sqrt(Math.sqrt(i))))),2)
After averaging those out a similar formula to the one above
Number of Averages: ((100)*USER_DEFINED_NUM_TESTS)*USER_DEFINED_NUM_FILES
Which in the test run by me would be (100*300*5) would be a total of 150,000 averages per machine
Those averages were then condensed into 15 different averages, (5 for the Level 1 loop, 5 for the level 1 recursive method, etc) from each file, which were then condensed into 1 average for each computer listed.
Due to my data collected I've determined that as Level approaches 5, recursion will surpass loops, in terms of efficiency
Totals
Computer 1: XP x86:
Time in nanoseconds to complete 3000 iterations
Loop Recursion
12,532........22,433
694,606.......716,099
1,077,739.....982,109
12,165........23,292
696,031.......715,903
1,077,635.....982,543
12,038........21,634
696,441.......718,188
1,077,286.....984,329
10,343........18,235
694,452.......710,979
1,076,967.....977,296
Computer 2: Win 7 x64:
11,312........50,795
78,332........142,507
2,471,795.....2,489,608
11,104........49,439
79,503........145,471
2,944,205.....2,844,139
13,195........59,060
91,282........179,496
2,993,883.....3,135,412
13,539........56,012
91,448........174,059
2,888,481.....3,092,689
11,104........49,439
79,503........145,471
2,944,205.....2,844,139
4.Graphs(Lower is better)
Computer 1: xp X86:
2.Computer 2: Win7 x64:
5.Code ran
1.The handler
public static void control(int runToDo) throws IOException
{
//if runToDo == 0, level 1 loop,
// ==3 level 2 loop
// ==4 level 3 loop
// ==1 level 1 recursion
// ==5 level 2 recursion
// ==2 level 3 recursion
double k = 3000;
for(int l = 0 ; l < 100; l ++){
if(runToDo == 0){
loopCheck(k);
}
else if(runToDo == 3)
loopCheck2(k);
else if(runToDo == 4)
loopCheck3(k);
else
recurCheck(k,runToDo);
}
tot3 += tot;//adds to the total avg
f.print(tot/(100)+" ");//prints avg to file
tot = 0; // resets it
}
using this method, I passed an int to runToDo which then ran the method that would generate averages. If that int called a recursive method it was passed to the recursion handler
public static void recurCheck(double run, int runToDo) throws IOException
{
long start = System.nanoTime();
if(runToDo == 1){
recurCheck2(run);
}
else if (runToDo == 5){
recurCheck3(run);
}
else{
recurCheck4(run);
}
long ending = System.nanoTime();
long total = ending - start;
tot += total;
f.flush();
}
Level 1 loop code
public static void loopCheck(double run) throws IOException
{
long start = System.nanoTime();
double calc = 0;
for(double i = 0 ; i < run;i++)
{
calc += 1;
}
long ending = System.nanoTime();
long total = ending - start;
tot += total;
f.flush();
}
Level 2 loop code
public static void loopCheck2(double run) throws IOException
{
long start = System.nanoTime();
double j = 0;
for(double i = 0 ; i < run;i++)
{
j += (double)(((int)(i * Math.sqrt(i*i - 4*i*i)) & 0xA)<<2);
}
long ending = System.nanoTime();
long total = ending - start;
tot += total;
f.flush();
}
Level 3 loop code
public static void loopCheck3(double run) throws IOException
{
long start = System.nanoTime();
double calc = 0, j = 0;
for(double i = 0 ; i < run;i++)
{
j += Math.pow(Math.sqrt(Math.sqrt(Math.pow(i/5, Math.sqrt(Math.sqrt(i))))),2);
}
long ending = System.nanoTime();
long total = ending - start;
tot += total;
f.flush();
}
Level 1 recursion code
public static double recurCheck2(double run)
{
if(run == 0)
return 0;
return 1 + recurCheck2(--run);
}
Level 2 recursion code
public static double recurCheck3(double run)
{
if(run == 0)
return 0;
return (double)(((int)(run * Math.sqrt(run*run - 4*run*run)) & 0xA)<<2) + recurCheck3(--run);
}
Level 3 recursion code
public static double recurCheck4(double run)
{
if(run == 0)
return 0;
return Math.sqrt(Math.sqrt(Math.sqrt(Math.pow(run/5, Math.sqrt(Math.sqrt(run)))))) + recurCheck4(--run);
}
This post has been edited by Locke: 27 June 2010 - 06:54 PM
Reason for edit:: Added some code/inline tags
MultiQuote
| 