Recursion versus Looping

Overview

In general, whatever problem you can solve with Recursion can also be solved with Looping (iteration).

It turns out, that for most use cases, Iteration (looping) performs better than Recursion

The problem with recursion, is that small results need to be computed many times. This makes it somewhat inefficient.

Looping can accomplish the same result – without being computationally expensive.

fibonacci

Summary

As you can see, recursion is almost 10,000 times as expensive as Looping. It gets more expensive as the computation increases (as N increases).

Here is the full source code, in C#

Example – Fibonacci  – Using Recursion

      private static int RecurseFibonacci(int f)
       
{
           
if (f <= 1)
               
return 1;
           
else
           
{
               
return RecurseFibonacci(f  1) + RecurseFibonacci(f  2);
           
}
       
}

Example – Fibonacci  – Using Looping

static int LoopFibonacci(int n)
       
{
           
int prev = 1; int first = 1; int next = 1;
           
           
if (n <= 1)
               
return 1;
           
else
           
{
               
for(int k=2; k<=n; k++)
               
{
                   
next = first + prev;
                   
first = prev;
                   
prev = next;
               
}

                return prev; 
           
}
       
}

 
   static void Main(string[] args)
       
{

            Stopwatch stopwatch = new Stopwatch();
           
stopwatch.Start();
           
int result1  = LoopFibonacci(f);
           
stopwatch.Stop();

            // Write hours, minutes and seconds.
            Console.WriteLine(” Computing Fibonacci for N = ” + f);
           
Console.WriteLine(“Fibonacci Result = ” + result1 + ” Loop Time:” + stopwatch.Elapsed.TotalMilliseconds + ” ms”);

            stopwatch.Start();
           
int result2 = RecurseFibonacci(f);
           
stopwatch.Stop();
           
// Write hours, minutes and seconds.
            Console.WriteLine(“Fibonacci Result = ” + result2 + ” Recursion Time: ” + stopwatch.Elapsed.TotalMilliseconds + ” ms”);

        }

Specializing in high volume web and cloud application architecture, Anuj Varma’s customer base includes Fortune 100 companies (dell.com, British Petroleum, Schlumberger).
Anuj’s training as a mathematical physicist followed by years of advanced computer programming is unique in the industry.

For Anuj’s popular technology seminars and science and scientific computing seminars, please visit ANUJ.COM

For Anuj’s Mathematical Models and Math Modeling related consulting , please visit anuj.com.

All content on this site is original and owned by AdverSite Web Holdings, Inc. – the parent company of anujvarma.com. No part of it may be reproduced without EXPLICIT consent from the owner of the content.

Anuj Varma – who has written posts on Anuj Varma, Technology Architect.


Leave a Reply

Your email address will not be published. Required fields are marked *