Page 1 of 1

## Recursion and You The efficiency of recursion Rate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=171509&amp;s=de215f7611fa38474753e7d61522782c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ianian112

• D.I.C Regular

Reputation: 118
• Posts: 378
• Joined: 28-November 09

Posted 01 May 2010 - 07:55 PM

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

Is This A Good Question/Topic? 1

Page 1 of 1

 Query failed: connection to localhost:3312 failed (errno=111, msg=Connection refused).