Iterative vs. Recursive approaches

5 בנובמבר 2007

תגיות:
13 תגובות

This article will discuss the performance overhead when dealing with recursive problem-solving approaches.


 


Recursive 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.  Some of the algorithms/functions can be represented in iterative way and some may not.


 


Iterative functions – are loop based imperative repetition of a process (in contrast to recursion which has more declarative approach).


 



Comparison between Iterative and Recursive approaches from performance considerations


Factorial:

        //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;
}

Remark: in this test I don't look at the results because int isn't capable of holding such big numbers.


























N Recursive Iterative
10 334 ticks 11 ticks
100 846 ticks 23 ticks
1000 3368 ticks 110 ticks
10000 9990 ticks 975 ticks
100000 stackoverflow 9767 ticks
 

As we can clearly see the recursive is a lot slower than the iterative (considerably) and limiting (stackoverflow).



The reason for the poor performance is heavy push-pop of the registers in the IL level of each recursive call.


 


Fibonacci:

        //————— 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 resultHistory =
new Dictionary();

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;
}


Remark:  in this test I don't look at the results because int isn't capable of holding such big numbers.

















































N Recursive Recursive opt. Iterative
5 5 ticks 22 ticks 9 ticks
10 36 ticks 49 ticks 10 ticks
20 2315 ticks 65 ticks 10 ticks
30 180254 ticks 61 ticks 9 ticks
100 Too long/overflow 158 ticks 11 ticks
1000 Too long/overflow 1470 ticks 27 ticks
10000 Too long/overflow 13873 ticks 190 ticks
100000 Too long/overflow Too long/overflow 3952 ticks
 

As before the recursive approach is worse than iterative however, we could apply memoization 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).



Summery


1.       Try not to use recursion in system critical locations


2.       Elegant solutions not always the best performing when used in "recursive situations".


3.       If you required to use recursion at least try to optimize it with dynamic programming approaches (such as memoization)


Source code @ CodeProject.com

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. (*) שדות חובה מסומנים

13 תגובות

  1. Simon6 בנובמבר 2007 ב 0:50

    I agree with the article, but there are a couple of points to think about:

    1. There are algorithms which you can't solve without recursion, and iteration approach can't be used at all. For instance, most of backtracking algorithms can't be solved without heavy use of recursion.

    2. There is a definition for algorithm complexity and memory complexity. In you cases you underline that recursive algorithms "eat" lots of memory because of the heavy work in stack, but sometimes, you agree to loose in performance of algorithm in order to gain in memory. (It depends on situation and given input, but it could happen), so sometimes, if one wants to get the best from both algorithm and memory complexity, one should try recursion approach and not iterative one.

    להגיב
  2. Eyal6 בנובמבר 2007 ב 9:23

    Hi Simon,

    1. I wrote and gave an example to acermann function that cannot be solved in iterative way(http://en.wikipedia.org/wiki/Ackermann_function).

    2. Agreed, i wanted to underline the importance of "thinking out of the box" in various common recursive solutions and using the iterative versions if posible or at least apply various optimizations inorder to achieve better "reponse time" (when memory is heavily loaded the GC is busy tring to collect free memory and the side effect is less responsive applications.

    להגיב
  3. Tuna Toksoz9 במרץ 2008 ב 11:04

    Hey Simon,
    Just to inform you, fibonacci numbers can be calculated with a single formula
    check this
    http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html

    להגיב
  4. Tuna Toksoz9 במרץ 2008 ב 11:06

    Even though I know this blogpost is just to show how recursion can be a bottleneck.

    להגיב
  5. Tuna Toksoz9 במרץ 2008 ב 11:11

    [quote]The reason for the poor performance is heavy push-pop of the registers in the IL level of each recursive call[/quote]

    Yes, this is one reason but more importantly you "recalculate" every step over and over again.

    for example
    f(5)=f(4)+f(3)
    / \
    f(3) f(2)
    / \
    f(2)f(1)

    As you see, f(3) and f(2) will be recalculated more than 1 times. For big numbers the number of "recalculations" will be hugeeee(I mean really hugee)

    Iteration removes this pain.

    And for artificial intelligence, recursion can be the only way.

    להגיב
  6. Eyal9 במרץ 2008 ב 11:18

    Hi Tuna Toksoz,

    Regarding your example (f(5)=f(4)+f(3)) – I used memoization to solve this (common) issue, see Recursive opt.

    להגיב
  7. Tuna Toksoz9 במרץ 2008 ב 19:16

    Oh, My bad. Sorry for that, I just missed the example and directly posted reply.

    Could I have seen you in Castle Forums?

    להגיב
  8. Eyal9 במרץ 2008 ב 19:24

    Unfortunatly I have very little time to write, so probabaly NO :-)

    להגיב
  9. חן אגוזי30 ביולי 2008 ב 7:17

    Note that at times, the recursive way is more expressive, and it's kinda easier to write recursion code in a more thread safe manner.

    Also, there are languages that are optimised to recursions, as most of the functional languages are. So when you're in F#/Erlang/PROLOG land, you are probably better of writing the recursive code, as it'd be more expressive, yet still with good performence

    להגיב
  10. Hasan6 בדצמבר 2009 ב 21:43

    How we can display the time difference in the program display

    reply me
    hasan4it@gmail.com

    להגיב
  11. moraa faith12 בפברואר 2010 ב 7:14

    when asked to name the best and worst case complexities of a factorial algorithm, what do you say?

    להגיב
  12. +122 במאי 2010 ב 10:20

    if u hate spaghetti code why on earth are you working for microsoft?!

    there are other places to work where simplicity is better appreciated and utilised.

    recursion == complexity

    להגיב
  13. 122 במאי 2010 ב 10:24

    if u hate spaghetti code why on earth are you working for microsoft?!

    there are other places to work where simplicity is better appreciated and utilised.

    recursion == complexity

    להגיב