So I’m currently in process of reading the infamous “Code Complete” by Steve McConnell. So far it’s been an amazing book and I definitely guarantee it to any programmer out there. I’ve just read the section on recursion and it mentioned how doing recursion for a factorial (or fibonacci) function is not as efficient as a for-loop iteration. I guess I never thought about it, since in computer science I was always shoved recursion down my throat when doing factorials. I agree with him that computer science professors are eager to apply the idea of recursion on factorials, but I’ve never remembered a professor mention that it’s not the most efficient way. McConnell states in the book that doing recursion in factorials:
- Is not as fast as a for-loop.
- Not as clear to read as a for-loop.
- Use of run-time memory is unpredictable.
Just for fun, I wanted to test his point on speed. This is a Python script that tests the average speed of a factorial using a for-loop or recursion. I noticed that for numbers less than 3000! the time it took for both functions were exactly the same. It was only when I bumped it up to 5000!, which is a huge number (16,327 digits). Luckily Python lets you work with very large numbers easily. Just had to increase the number of recursion calls in Python from the default 1000.
import win32api import sys sys.setrecursionlimit(10000) def factorial_forloop( n ): count = 1 for i in range( n, 0, -1 ): count = count * i return count def factorial_recursion(n): if n == 0: return 1 else: return n * factorial_recursion(n-1) total_time_recursion = 0 total_time_forloop = 0 number_of_tries = 500 for i in range( 1, number_of_tries ): start = win32api.GetTickCount() factorial_recursion( 5000 ) end = win32api.GetTickCount() total = end - start total_time_recursion += total start = win32api.GetTickCount() factorial_forloop( 5000 ) end = win32api.GetTickCount() total = end - start total_time_forloop += total print "\n" print "Average time for recursion: ", ( total_time_recursion / 10 ) * .001 print "Average time for for-loop: ", ( total_time_forloop / 10 ) * .001
So in 500 tries, the results were as follows:
Average time for recursion: 1.284 seconds Average time for for-loop: 1.083 seconds
It doesn’t seem by much but the results are interesting. But then again, a factorial is a very simple algorithm. In future posts I’ll try to test more complicated algorithms and see how they battle out. Also, this is Python. The results for C, C++, or Java may differ.