Recursion. It’s one of those questions you see in most interview questions. Usually it’s in the context of something like ‘Calculate Fibonacci numbers’ or something along those lines with the intent of determining if you understand recursion. Its a great question to ask but at the same time the answer itself is actually very wrong if you were going to do it in the real world.
Recursion has it’s place (Sorts, Binary Tree traversal, etc) but don’t just use it because it makes the code smaller. Think about the cost of recursion. Every call:
- Adds an object to the call stack
- Allocates more memory
- Sometimes throws readability right out the window (and down the block, making a left at the mailbox)
- Eats up CPU time
A coworker of mine (Jay Palat) just recently wanted to dust off his python skills. To do this he decided to code a fun little problem: Get a list of all the even Fibonacci numbers. Now, being a good developer he immediately took to it with recursion like so:
#!/usr/bin/python
"""Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued term"""
def fib(n):
if n == 0 :
return 1
if n == 1 :
return 2
return fib(n-1) + fib(n-2)
"""for n in range(0,10):
print fib(n)
"""
item = 0
sum = 0
fib_item = fib(item)
while fib_item < 40000000:
if fib_item%2==0:
print "Even item: " + str(fib_item)
sum = sum + fib_item
item = item + 1
fib_item = fib(item)
print "Sum: " + str(sum)
print "Final item : " + str(item)
Don’t worry about the style or overall approach. The thing to know is that this method, which I dare say most developers would take, uses recursion. In the end this method took, on average, 47 seconds to execute (going up to 40000000).
For each call you have two recursive calls. This means you have at least three entries on the call stack per call, which then has three, and then three…. welcome to recursion. Honestly, we discussed the Big O on this and realized we weren’t that good at Big O and moved on 😉
I then said: ‘Why not do it without recursion? Sure it might not be as cool, might not be as small, but is should use a lot less memory and CPU’.
This is what was coded (stripped down):
old_number = 1
current_number = 1
next_number = 0
sum = 0
while current_number < 40000000:
print current_number
if current_number%2 == 0:
sum = sum + current_number
next= current_number + old_number
old_number = current_number
current_number = next
print "Sum :" + str(sum)
And the total execution time for this : 0.027 seconds.
Lets state that again:
Old way with recursion: 47 seconds
New way without recursion: 0.027 seconds
Without the recursion we didn’t have the stack overhead, the additional memory usage, or any of the additional CPU cycles.
So, the next time you think of recursion, think of performance as well. You might even respond in the interview: “Do you want me to just show recursion, or do you want me to make it fast and efficient?”
