Python Recursion

Board Discussion Number 2

Page 1 of 1

14 Replies - 7955 Views - Last Post: 21 December 2010 - 05:57 AM Rate Topic: -----

#1 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Python Recursion

Post icon  Posted 15 December 2010 - 12:56 PM

*
POPULAR

Recursion is a touchy subject. I've met some people who say you should never ever use it. I'll admit I'm not a big fan of recursion but I really love the topic because it's so controversial!

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 :walkman:

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


Is This A Good Question/Topic? 5
  • +

Replies To: Python Recursion

#2 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1253
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Python Recursion

Posted 15 December 2010 - 02:01 PM

I'm not that familiar with Python to leave an educated response on the subject here. But I will say this: Please don't take this as a sign to use recursion everywhere you can. Just because you can doesn't mean you should.

Basically: Readable code > Clever code. Don't be clever or you'll annoy every other developer on your team.
Was This Post Helpful? 0
  • +
  • -

#3 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Python Recursion

Posted 15 December 2010 - 02:19 PM

I agree with you whole heartedly. Remember Sergio, I tried to be very clear that recursion beating iteration is a RARE occurrence! In 99% of cases, iteration will win. For example:

def fibR(num):
    if num < 2:
        return num
    return fibR(num-1) + fibR(num-2)

def fibI(num):
    secondPrev, prev = 1,1
    for i in range(num-2):
        secondPrev, prev = prev, secondPrev+prev
    return prev       
        


The recursive version of the Fibonacci algorithm is far less efficient. The iterative version can calculate fibonacci(500) in moments, but I stopped the recursive one after running for 10 minutes without any answer.

This post is intended to serve as a proof of concept and a discussion starter. If you drastically change your style based on it, you definitely misread something.

This post has been edited by atraub: 15 December 2010 - 02:22 PM

Was This Post Helpful? 0
  • +
  • -

#4 Locke  Icon User is offline

  • Sarcasm Extraordinaire!
  • member icon

Reputation: 521
  • View blog
  • Posts: 5,596
  • Joined: 20-March 08

Re: Python Recursion

Posted 15 December 2010 - 03:25 PM

I remember the days of Fibonacci recursion assignments in Java. The thing wouldn't find the 20th number in any reasonable amount of time. :D

Iteration FTW!
Was This Post Helpful? 0
  • +
  • -

#5 xclite  Icon User is offline

  • LIKE A BOSS
  • member icon


Reputation: 906
  • View blog
  • Posts: 3,171
  • Joined: 12-May 09

Re: Python Recursion

Posted 15 December 2010 - 03:27 PM

View PostSergio Tapia, on 15 December 2010 - 05:01 PM, said:

I'm not that familiar with Python to leave an educated response on the subject here. But I will say this: Please don't take this as a sign to use recursion everywhere you can. Just because you can doesn't mean you should.

Basically: Readable code > Clever code. Don't be clever or you'll annoy every other developer on your team.


Sometimes the most readable and elegant solution to a problem is recursive rather than iterative =p
Was This Post Helpful? 1
  • +
  • -

#6 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2021
  • View blog
  • Posts: 4,191
  • Joined: 11-December 07

Re: Python Recursion

Posted 15 December 2010 - 03:36 PM

You are correct but only in the same way an insertion sort is quicker than a quick sort for small lists. I'd be interested if this version was fastest:


def shortcutIterativeFunction(num):
        if num <= 5 : return num
        while num <= 5:
            x = num**25
            num += 3
        return num


This post has been edited by cfoley: 15 December 2010 - 03:36 PM

Was This Post Helpful? 0
  • +
  • -

#7 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1253
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Python Recursion

Posted 15 December 2010 - 03:37 PM

View Postatraub, on 15 December 2010 - 04:19 PM, said:

This post is intended to serve as a proof of concept and a discussion starter. If you drastically change your style based on it, you definitely misread something.


I know, but if I just agree with what you say that's not much of a discussion right?
Was This Post Helpful? 0
  • +
  • -

#8 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2874
  • View blog
  • Posts: 11,032
  • Joined: 15-July 08

Re: Python Recursion

Posted 15 December 2010 - 03:40 PM

View PostLocke, on 15 December 2010 - 04:25 PM, said:

I remember the days of Fibonacci recursion assignments in Java. The thing wouldn't find the 20th number in any reasonable amount of time. :D

Iteration FTW!


I made a recursive Fibonacci that was MUCH faster than the iterative version with higher numbers, but slower with lower numbers by implementing an algorithm the stores the result of one of the Fibonacci in an array. Then, if I have had fib(2) and fib(3) stored in the array, then I don't have to calculate those values more than once ever. It was a neat algorithm.

In that rare case, with large numbers, the recursive version was faster, but it used more space.
Was This Post Helpful? 0
  • +
  • -

#9 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Python Recursion

Posted 15 December 2010 - 06:41 PM

Sorry cfoley, truth is your assertion is founded on a false premise. If Python built the while loop when it executed it, you'd be correct. However, Python builds the loop when the function is called. Your algorithm is actually the least efficient of the 3 because all it does is add an extra conditional.

Average speed with Recursion:  0.0382499814034
Average speed with iteration:  0.0428500056267
Average speed with Short itr:  0.0441500186920

Average speed with Recursion:  0.0391499757767
Average speed with iteration:  0.0418500185013
Average speed with Short itr:  0.0430999994278

Average speed with Recursion:  0.0394500255585
Average speed with iteration:  0.0422500133514
Average speed with Short itr:  0.0446999669075

Average speed with Recursion:  0.0393499612808
Average speed with iteration:  0.0422000169754
Average speed with Short itr:  0.0440499901772

Average speed with Recursion:  0.0393500089645
Average speed with iteration:  0.0422000288963
Average speed with Short itr:  0.0447499752045

Average speed with Recursion:  0.0397999882698
Average speed with iteration:  0.0423499941826
Average speed with Short itr:  0.0438499927521

Average speed with Recursion:  0.0393500328064
Average speed with iteration:  0.0424999833107
Average speed with Short itr:  0.0443999767303

Average speed with Recursion:  0.0389000058174
Average speed with iteration:  0.0422499895096
Average speed with Short itr:  0.043699991703

Average speed with Recursion:  0.0390999913216
Average speed with iteration:  0.0424000024796
Average speed with Short itr:  0.0444499731064

Average speed with Recursion:  0.0389500141144
Average speed with iteration:  0.0422500014305
Average speed with Short itr:  0.0435999989510


This post has been edited by atraub: 16 December 2010 - 11:54 AM

Was This Post Helpful? 1
  • +
  • -

#10 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 611
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Python Recursion

Posted 16 December 2010 - 09:54 AM

Wait, recursion is a touchy and controversial subject? Wow, Python sure is a different crowd than I'm used to!

Of course, recursion is dangerous in many situations in Python due to lack of TCO (tail call optimization), which means that recursion can quite easily blow the stack in Python. Too bad Guido is a stubborn old fart. :P
Was This Post Helpful? 0
  • +
  • -

#11 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Python Recursion

Posted 16 December 2010 - 11:43 AM

I personally think Guido raises a fair argument. TRE could break pre-existing code and would cause Python to be less.......... "Pythonic" haha,

This post has been edited by atraub: 17 December 2010 - 07:54 AM

Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,705
  • Joined: 16-October 07

Re: Python Recursion

Posted 16 December 2010 - 05:15 PM

View PostDogstopper, on 15 December 2010 - 04:40 PM, said:

I made a recursive Fibonacci that was MUCH faster than the iterative version with higher numbers, but slower with lower numbers by implementing an algorithm the stores the result of one of the Fibonacci in an array.



Funny you should mention that. I was thinking of doing a writeup on decorators, but I'm too lazy.

So, a quick intro to the funkiness of python decorators. Imagine you could just throw a tag on a recursive function and memoize it? Well...
import time
import random

def fibR(num):
	if num < 2:
		return num
	return fibR(num-1) + fibR(num-2)


def fibI(num):
	secondPrev, prev = 1,1
	for i in range(num-2):
		secondPrev, prev = prev, secondPrev+prev
	return prev      


class MemoN():
	def __init__(self, func):
		self.func = func
		self.cache = dict()
	def __call__(self, n):
		if n not in self.cache:
			self.cache[n] = self.func(n)
		return self.cache[n]

@MemoN
def fibR2(num):
	if num < 2:
		return num
	return fibR2(num-1) + fibR2(num-2)

def testAll(num):
	print("num = %d" % num)
	for name, func in [ ("fibR", fibR), ("fibI", fibI), ("fibR2", fibR2) ]:
		start = time.time() 
		result = func(num)
		print("\t%s\t%f\t%d" % (name, time.time() - start, result))

for num in range(5, 31, 5):
	testAll(num)




Results:
num = 5
	fibR	0.000012
	fibI	0.000008
	fibR2	0.000028
num = 10
	fibR	0.000074
	fibI	0.000006
	fibR2	0.000024
num = 15
	fibR	0.003919
	fibI	0.000018
	fibR2	0.000033
num = 20
	fibR	0.017732
	fibI	0.000021
	fibR2	0.000036
num = 25
	fibR	0.125473
	fibI	0.000016
	fibR2	0.000029
num = 30
	fibR	0.776999
	fibI	0.000014
	fibR2	0.000024




As to the catchup over time...
def testSome(num):
	def tf(f):
		start = time.time() 
		f(num)
		return time.time() - start
	print("%d\t%f\t%f" % (num, tf(fibI), tf(fibR2)))

print("   \t%s\t\t%s" % ("fibI", "fibR2"))
for num in range(100, 1000, 50):
	testSome(num)



   	fibI		fibR2
100	0.000061	0.002048
150	0.000092	0.000364
200	0.000108	0.000357
250	0.000135	0.000369
300	0.000167	0.000387
350	0.000206	0.000449
400	0.000269	0.008277
450	0.000274	0.000405
500	0.000278	0.000388
550	0.000311	0.000459
600	0.000340	0.000393
650	0.000371	0.005374
700	0.000510	0.000434
750	0.000436	0.000403
800	0.000478	0.004959
850	0.000532	0.000423
900	0.000538	0.000396
950	0.000581	0.000397



You can't actually go much deeper than that in Python by default. There is a recursion depth governor.

This post has been edited by baavgai: 16 December 2010 - 05:16 PM

Was This Post Helpful? 1
  • +
  • -

#13 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2874
  • View blog
  • Posts: 11,032
  • Joined: 15-July 08

Re: Python Recursion

Posted 16 December 2010 - 06:01 PM

That is a great example on decorators! I have never fully understood it until I saw this practical example. Even better that it memoizes! Great example baavgai. To do deeper tests, can't you sys.setrecursionlimit(bigger_num)?
Was This Post Helpful? 0
  • +
  • -

#14 Guest_notax*


Reputation:

Re: Python Recursion

Posted 20 December 2010 - 11:37 PM

without recursion
:D

...
p = (1 + 5**0.5)/2
fib3 = lambda n:  int(round((p**n - (1-p)**n) / 5**0.5))


def testAll(num):
    print("num = %d" % num)
    for name, func in [ ("fibR", fibR), ("fibI", fibI), ("fibR2", fibR2), ("fib3", fib3) ]:
        start = time.time()
        result = func(num)
        print("\t%s\t%f\t%d" % (name, time.time() - start, result))
	 
for num in range(5, 31, 5):
    testAll(num)



num = 5
fibR 0.000020 5
fibI 0.000019 5
fibR2 0.000057 5
fib3 0.000022 5
num = 10
fibR 0.000127 55
fibI 0.000013 55
fibR2 0.000055 55
fib3 0.000013 55
num = 15
fibR 0.001376 610
fibI 0.000023 610
fibR2 0.000055 610
fib3 0.000020 610
num = 20
fibR 0.016085 6765
fibI 0.000030 6765
fibR2 0.000074 6765
fib3 0.000021 6765
num = 25
fibR 0.189645 75025
fibI 0.000037 75025
fibR2 0.000084 75025
fib3 0.000023 75025
num = 30
fibR 2.144253 832040
fibI 0.000040 832040
fibR2 0.000074 832040
fib3 0.000023 832040
Was This Post Helpful? 0

#15 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,705
  • Joined: 16-October 07

Re: Python Recursion

Posted 21 December 2010 - 05:57 AM

Cute. However, you're kind of missing the point of the thread.

I'll play along, since the thread seems to have run course. Two things: Globals are bad and floating point is fickle.

Written more nicely.
import time

def fibI(num):
	secondPrev, prev = 1,1
	for i in range(num-2):
		secondPrev, prev = prev, secondPrev+prev
	return prev      

def fib3(num):
	c = 5**0.5
	p = (1 + c)/2
	return int(round((p**num - (1-p)**num) / c))

def testPair(num):
	def test(name, func):
		start = time.time()
		result = func(num)
		print("\t%s\t%f\t%d" % (name, time.time() - start, result))
		return result
	
	print("\nnum = %d" % num)
	r1 = test("fibIter", fibI)
	r2 = test("fibMath", fib3)
	if r1==r2:
		print("\tmatch")
	else:
		print("\tmath FAIL")

for num in range(5, 81, 5): 
	testPair(num)



Results:
num = 60
	fibIter	0.000029	1548008755920
	fibMath	0.000011	1548008755920
	match

num = 65
	fibIter	0.000030	17167680177565
	fibMath	0.000011	17167680177565
	match

num = 70
	fibIter	0.000031	190392490709135
	fibMath	0.000011	190392490709135
	match

num = 75
	fibIter	0.000033	2111485077978050
	fibMath	0.000015	2111485077978055
	math FAIL

num = 80
	fibIter	0.000035	23416728348467685
	fibMath	0.000011	23416728348467744
	math FAIL



Yeah, the approximation is faster, but for most functions accuracy is more important. :P
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1