Recursion versus Iteration ( Looping )

This entry is part 3 of 3 in the series algorithms

algorithms

The Under-Appreciated Hash Function–Illustrated using a Birthday Lookup
Swapping without a temp variable
Recursion versus Iteration ( 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.

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”);

}

Anuj holds professional certifications in Google Cloud, AWS as well as certifications in Docker and App Performance Tools such as New Relic. He specializes in Cloud Security, Data Encryption and Container Technologies.

Initial Consultation

Anuj Varma – who has written 1214 posts on Anuj Varma, Hands-On Technology Architect, Clean Air Activist.