New Topic/Question
Reply
Posted 15 December 2010 - 12:56 PM
Not that long ago, I had an 'enthusiastic disagreement' with another programmer about recursion. I made an assertion that some of you may feel is quite crazy. I theorized that in some very rare situations, recursion could be more efficient than iteration. I think I just heard someone's brain explode
Imagine a situation where you have a function, and less than 5% of the time that function would need to do a repetitious operation. In that situation, you could place this 'repetitious operation' in a loop, or you could make it recursive. It is my belief that in Python (and perhaps SOME other interpreted languages) this operation might be completed faster using recursion. The reason is that there is some overhead in creating a loop regardless as to whether it's used, but unused recursive function calls have no overhead. If I'm not being clear, let me show you a short program I wrote to express my idea.
"""
Recursion test
A proof of concept program used to demonstrate that recursion can be
more efficient than looping in some scenarios.
atraub
12/14/2010
"""
import time
import random
#Records the elapsed time during testing
#numList is a list of integers and 'theFunction' is a function object
def test(numList, theFunction):
start = time.time()
for item in numList:
theFunction.__call__(item)
end = time.time()
return end - start #elapsed time in seconds
#in a rare scenario, do some substantial math, then loop
#Note, the loop is always created even if it's not used.
def iterativeFunction(num):
while num <= 5:
x = num**25
num += 3
return num
#in a rare scenario, do some substantial math, then make a recursive call
def recursiveFunction(num):
if num <= 5:
x= num**25
return recursiveFunction(num+3)
return num
#Create 'count' numbers between low and high and return a list holding them
def createNumList(count=100000, low=1, high=200):
numList = []
for i in range(count):
numList.append(random.randint(low,high))
return numList
#Run the tests 'testCount' times and take the average for each
def main(testCount=20):
recurTime = []
iteraTime = []
for i in range(testCount):
x = createNumList()
iteraTime.append(test(x,iterativeFunction))
recurTime.append(test(x,recursiveFunction))
print("Average speed with Recursion: ",sum(recurTime)/len(recurTime))
print("Average speed with iteration: ",sum(iteraTime)/len(iteraTime))
#main * 10!
def thoroughTest():
for i in range(10):
print("")
main()
The recursive function and the iterative function are essentially identical except for how they do repetitious operations. Every time the iterative function is called, a loop structure will be created which has some tiny overhead. When the recursive function is called, this 'loop overhead' is not present, and the recursion is only used a small percent of the time. I theorized that in a rare situation like this, over time the 'loop overhead' would cause the iterative function to perform worse than the recursive style. I realize that this claim may seem outrageous to some, but the numbers don't lie. Here are my results from a thoroughTest.
#Code tags nicely preserved formatting Average speed with Recursion: 0.0367999911308 Average speed with iteration: 0.0410499811172 Average speed with Recursion: 0.0368499994278 Average speed with iteration: 0.0406000137329 Average speed with Recursion: 0.0377000212669 Average speed with iteration: 0.0403499960899 Average speed with Recursion: 0.0377499461174 Average speed with iteration: 0.040750014782 Average speed with Recursion: 0.0367999911308 Average speed with iteration: 0.0407500386238 Average speed with Recursion: 0.0363499641418 Average speed with iteration: 0.0402500033379 Average speed with Recursion: 0.0362499833107 Average speed with iteration: 0.0396999955177 Average speed with Recursion: 0.038150036335 Average speed with iteration: 0.0412499904633 Average speed with Recursion: 0.0391500115395 Average speed with iteration: 0.0430000066757 Average speed with Recursion: 0.0380500078201 Average speed with iteration: 0.0418999791145
Essentially, my argument can be boiled down to this: Setting up 100,000 loops and using them 3000 times will be more expensive than making approx. 3,000 recursive calls. I know this is a controversial topic, so I really want to invite people to speak up and voice their thoughts! I'm not afraid of being wrong and so long as we keep it respectful, no one should feel insulted. There's a good chance that I'm misinterpreting data, but I'd love to find out what everyone thinks!
TRE
For those of you who think that we're witnessing tail recursion elimination, I should warn you that Guido has openly said that Python does not support tail recursion elimination and it likely never will.
This post has been edited by atraub: 19 July 2012 - 03:03 PM
MultiQuote
| 