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:

1. Is not as fast as a for-loop.
2. Not as clear to read as a for-loop.
3. 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.