Semaphore - ParaZz Blog

Loops vs. Recursion

7 September 2017 • Paras Sharma

We use recursion and loops in solving many programming problems (almost all).

But how do they compare with each other? Is using recursion instead of loops a great idea or should use iterative solution over recursive solution?

I had these questions from very long time in my mind. To get the answer I tried a perfomance test between iterative and recursive solution. I chose binary search as the benchmark (because it is faster for large number of elements). Let’s see which one is better.

Below are two function, one is iterative binary search and other is recursive binary search.

Binary Search (Loop and Recursion): Performance Measurement:

Output:

$ python3 metrics.py

Testing for 100 items
-----
Time Take by loop: 8.668698137626052e-05
Time Take by recursion: 0.00011143798474222422
Testing for 100 items
-----
Time Take by loop: 8.37119878269732e-05
Time Take by recursion: 0.00011085800360888243
Testing for 10000 items
-----
Time Take by loop: 0.00017785700038075447
Time Take by recursion: 0.00023082000552676618
---
Average t1/t2: 0.768

We can clearly see that iterative approach is around 70 times faster than recursion.

Also recursion process involves multiple stack push and pop, therefore there are chances of reaching a maximum recursion limit and even can lead to segmentation fault in unix-linux.

But we cannot ignore the the power of recursion, there are many problems which can only be solved via recusion approach, but according to me while formulating solution we should set iterative method as our primary approach.