|
|
<html>
<head>
<title>The Code Project</title>
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type=text/css href="http://www.codeproject.com/styles/global.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<pre>
Title: Iterative vs. Recursive approaches
Author: Eyal Lantzman
Email: lantzman@gmail.com
Member ID: 1551741
Language: C# 2.0
Platform: Windows
Technology: .NET 2.0+
Level: Beginner, Intermediate
Description: Is recursion the only option. See potential pitfalls and posible solutions
Section General .NET
SubSection C# Algorithms
</pre>
<h2>Introduction</h2>
<p>Originaly posted at <a href="http://blogs.microsoft.co.il/blogs/eyal/archive/2007/11/05/iterative-vs-recursive-approaches.aspx">blogs.microsoft.co.il/blogs/Eyal</a>
<p><a href="http://en.wikipedia.org/wiki/Recursion">Recursive</a> functions
� is a function that partially defined by itself and consists of some simple
case with a known answer. Example: Fibonacci number sequence, factorial function, quick sort and more. <br>Some of the algorithms/functions can be
represented in iterative way and some <a
href="http://en.wikipedia.org/wiki/Ackermann_function">may not</a>.</p>
<p><a href="http://en.wikipedia.org/wiki/Iterative">Iterative</a> functions
� are loop based imperative repetition of a process (in contrast to recursion
which has more declarative approach).</p>
<h2>Comparison between Iterative and Recursive approaches from performance considerations</h2>
<p ><b>Factorial:
</b></p>
<pre lang=cs>
//recursive function calculates n!
static int FactorialRecursive(int n)
{
if (n <= 1) return 1;
return n * FactorialRecursive(n - 1);
}
//iterative function calculates n!
static int FactorialIterative(int n)
{
int sum = 1;
if (n <= 1) return sum;
while (n > 1)
{
sum *= n;
n--;
}
return sum;
}
</pre>
<table width=300>
<tr bgcolor="gray">
<td><b>N</b></td>
<td><b>Recursive</b></td>
<td><b>Iterative</b></td>
</tr>
<tr >
<td>10</td>
<td>334 ticks</td>
<td>11 ticks</td>
</tr><tr>
<td>100</td>
<td>846 ticks</td>
<td>23 ticks</td>
</tr><tr>
<td>1000</td>
<td>3368 ticks</td>
<td>110 ticks</td>
</tr><tr>
<td>10000</td>
<td>9990 ticks</td>
<td>975 ticks</td>
</tr><tr>
<td>100000</td>
<td><font color="red">stack overflow</font></td>
<td>9767 ticks</td>
</tr>
</table>
<p><b>As we can clearly see the recursive is a lot slower than the iterative (considerably) and limiting (stackoverflow).</b></p>
<p>
The reason for the poor performance is heavy push-pop of the registers in the ill level of each recursive call.
</p>
<p> </p>
<p> </p>
<p ><b>Fibonacci:
</b></p>
<pre lang=cs>
//--------------- iterative version ---------------------
static int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
//--------------- naive recursive version ---------------------
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n - 1) +
FibonacciRecursive(n - 2);
}
//--------------- optimized recursive version ---------------------
static Dictionary<int, int> resultHistory =
new Dictionary<int, int>();
static int FibonacciRecursiveOpt(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (resultHistory.ContainsKey(n))
return resultHistory[n];
int result = FibonacciRecursiveOpt(n - 1) +
FibonacciRecursiveOpt(n - 2);
resultHistory[n] = result;
return result;
}
</pre>
<table width=500>
<tr bgcolor="gray"><td>N</td><td>Recursive</td><td>Recursive opt.</td><td>Iterative</td></tr>
<tr><td>5</td><td>5 ticks</td><td>22 ticks</td><td>9 ticks</td></tr>
<tr><td>10</td><td>36 ticks</td><td>49 ticks</td><td>10 ticks</td></tr>
<tr><td>20</td><td>2315 ticks</td><td>61 ticks</td><td>10 ticks</td></tr>
<tr><td>30</td><td>180254 ticks</td><td>65 ticks</td><td>10 ticks</td></tr>
<tr><td>100</td><td><font color="red">too long/stack overflow</font></td><td>158 ticks</td><td>11 ticks</td></tr>
<tr><td>1000</td><td><font color="red">too long/stack overflow</font></td><td>1470 ticks</td><td>27 ticks</td></tr>
<tr><td>10000</td><td><font color="red">too long/stack overflow</font></td><td>13873 ticks
</td><td>190 ticks
</td></tr>
<tr><td>100000</td><td><font color="red">too long/stack overflow</font></td><td><font color="red">too long/stack overflow</font></td><td>3952 ticks</td></tr>
</table>
<p>
As before the recursive approach is worse than iterative however, we
could apply <a href="http://en.wikipedia.org/wiki/Memoization">
memoization
</a> pattern (saving previous results in dictionary
for quick key based access), although this pattern isn't match for iterative approach
(but definitely improvement over the simple recursion). </p>
<h2>Notes</h2>
<p>1. The calculations may be wrong in big numbers, however the algorithms should be correct.</p>
<p>2. For timer calculations i used System.Diagnostics.Stopwatch.</p>
<br/>
<h2>Points of Interest</h2>
<p>1. Try not to use recursion in system critical locations.</p>
<p>2. Elegant solutions not always the best performing when used in "recursive situations".</p>
<p>3. If you required to use
recursion at least try to optimize it with <a
href="http://en.wikipedia.org/wiki/Dynamic_programming">dynamic programming</a>
approaches (such as <a href="http://en.wikipedia.org/wiki/Memoization">memoization</a>)</p>
<h2>History</h2>
<p>Post: November 05, 2007</p>
</body>
</html>
|
By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.
If a file you wish to view isn't highlighted, and is a text file (not binary), please
let us know and we'll add colourisation support for it.
In the last couple of years I'm working as Microsoft sub contractor in various project types - LOB, applications, CnC applications and Distributed applicaitons all of them considered to be extra large in tems of man power (or brain power), duration and geographic destribution between connected sites.
Submit an article or tip