Click here to Skip to main content
15,867,934 members
Articles / Programming Languages / C#

Iterative vs. Recursive Approaches

Rate me:
Please Sign up or sign in to vote.
4.11/5 (31 votes)
5 Nov 2007CPOL2 min read 260K   391   28   11
Implication of not thinking of iterative solutions over recursive from performance (response time) point of view

Introduction

This article was originally posted at blogs.microsoft.co.il/blogs/Eyal.

Recursive function – is a function that is 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 an iterative way and some may not.

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

Comparison between Iterative and Recursive Approaches from Performance Considerations

Factorial

C#
//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;
}
NRecursiveIterative
10334 ticks11 ticks
100846 ticks23 ticks
10003368 ticks110 ticks
100009990 ticks975 ticks
100000stack overflow9767 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 ill level of each recursive call.

Fibonacci

C#
//--------------- 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> resultHistory = new Dictionary<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;
}
NRecursiveRecursive opt.Iterative
55 ticks22 ticks9 ticks
1036 ticks49 ticks10 ticks
202315 ticks61 ticks10 ticks
30180254 ticks65 ticks10 ticks
100too long/stack overflow158 ticks11 ticks
1000too long/stack overflow1470 ticks27 ticks
10000too long/stack overflow13873 ticks 190 ticks
100000too long/stack overflowtoo long/stack overflow3952 ticks

As before, the recursive approach is worse than iterative however, we could apply memorization pattern (saving previous results in dictionary for quick key based access), although this pattern isn't a match for the iterative approach (but definitely an improvement over the simple recursion).

Notes

  1. The calculations may be wrong in big numbers, however the algorithms should be correct.
  2. For timer calculations, I used System.Diagnostics.Stopwatch.

Points of Interest

  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 memorization).

History

  • Post: November 06, 2007

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Taldor
Israel Israel
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.

Comments and Discussions

 
QuestionAcademic solution - How about a real world example? Pin
Russell Mangel30-Oct-18 0:13
Russell Mangel30-Oct-18 0:13 
QuestionNice Post Pin
Member 1120899119-Nov-14 6:58
Member 1120899119-Nov-14 6:58 
please find my version here:

http://www.samplecoder.com/2014/11/difference-between-recursion-and.html[^]
GeneralIt's a question of data structure Pin
virtuPIC15-Nov-07 20:45
virtuPIC15-Nov-07 20:45 
Generalblame C#, not .NET. F# does it better. Pin
Jay R. Wren13-Nov-07 2:00
Jay R. Wren13-Nov-07 2:00 
GeneralRe: blame C#, not .NET. F# does it better. Pin
ncarey13-Nov-07 7:29
ncarey13-Nov-07 7:29 
GeneralHum Pin
Steve Messer6-Nov-07 5:06
Steve Messer6-Nov-07 5:06 
GeneralRe: Hum Pin
Eyal Lantzman6-Nov-07 20:08
Eyal Lantzman6-Nov-07 20:08 
GeneralGood Job Pin
merlin9816-Nov-07 4:24
professionalmerlin9816-Nov-07 4:24 
GeneralGood Best Practice Pin
The DevMan6-Nov-07 0:33
The DevMan6-Nov-07 0:33 
GeneralInteresting Pin
NormDroid5-Nov-07 21:46
professionalNormDroid5-Nov-07 21:46 
GeneralRe: Interesting Pin
Eyal Lantzman5-Nov-07 22:32
Eyal Lantzman5-Nov-07 22:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.