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.<\/p>\n
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:<\/p>\n
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:<\/p>\n
\r\n#!\/usr\/bin\/python\r\n\r\n"""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:\r\n\r\n1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\r\n\r\nBy considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued term"""\r\n\r\ndef fib(n):\r\n if n == 0 :\r\n return 1\r\n if n == 1 :\r\n return 2\r\n return fib(n-1) + fib(n-2)\r\n \r\n"""for n in range(0,10):\r\n print fib(n)\r\n"""\r\nitem = 0\r\nsum = 0\r\nfib_item = fib(item)\r\nwhile fib_item < 40000000:\r\n if fib_item%2==0:\r\n print "Even item: " + str(fib_item)\r\n sum = sum + fib_item\r\n item = item + 1\r\n fib_item = fib(item)\r\nprint "Sum: " + str(sum)\r\nprint "Final item : " + str(item) \r\n<\/pre>\nDon’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).<\/p>\n
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 \ud83d\ude09<\/p>\n
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’.<\/p>\n
This is what was coded (stripped down):<\/p>\n
\r\nold_number = 1\r\ncurrent_number = 1\r\nnext_number = 0\r\nsum = 0\r\nwhile current_number < 40000000:\r\n print current_number\r\n if current_number%2 == 0:\r\n sum = sum + current_number\r\n next= current_number + old_number\r\n old_number = current_number\r\n current_number = next\r\n \r\nprint "Sum :" + str(sum)\r\n<\/pre>\nAnd the total execution time for this : 0.027 seconds.<\/p>\n
Lets state that again:
\nOld way with recursion: 47 seconds
\nNew way without recursion: 0.027 seconds<\/p>\nWithout the recursion we didn’t have the stack overhead, the additional memory usage, or any of the additional CPU cycles.<\/p>\n
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?”<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading