Iteration vs. Recursion in Python
For the past week at Hacker School, I took a step back from making a cool and awesome projects like the Vector Projector or the Japan Earthquake projects and looked at some good, old-fashioned computer science concepts. Much of what I did was repetive; I found a really simple problem, solved it using some method, and then tried solving it again using a variety of other methods. One project I worked on was programming the n'th Fibonacci number using python. In this blog I will describe iterative and recursive methods for solving this problem in Python.
What are Fibonacci numbers (or series or sequence)? From the Fibonacci Wiki Page, the Fibonacci sequence is defined to start at either 0 or 1, and the next number in the sequence is one. Each subsequent number in the sequence is simply the sum of the prior two. Hence the Fibonacci sequence looks like:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...
It is mathmatically defined as:
F(n) = F(n-1) + F(n-2)
My first approach was an iterative method -- basically, hardwire the case for F(0) and F(1), and then iteratively add the the values for larger values of n:
def F_iter(n): if (n == 0): return 0 elif (n == 1): return 1 elif (n >1 ): fn = 0 fn1 = 1 fn2 = 2 for i in range(3, n): fn = fn1+fn2 fn1 = fn2 fn2 = fn return fn else: return -1
OK, great, this works just fine... Now, let's try writing this recursively. You may ask, what is recursion in computer science? -- I certainly did about a week ago. Recursion, according to the Recursion Wiki page is a method where the solution to a problem depends on solutions to smaller instances of the same problem. Computer programs support recursion by allowing a function to call itself (Woa! -- this concept blew my mind).
A recursive solution to find the nth Fibonacci number is:
def F(n): if (n == 0): return 0 elif (n == 1): return 1 elif (n > 1): return (F(n-1) + F(n-2)) else: return -1
Notice that the recursive approach still defines the F(0) and F(1) cases. For cases where n > 1, however, the function calls itself. Let's take a look at what is happening here. Suppose we call F(4). F(4) will forgo the n = 0 and n = 1 cases and go the the n > 1 case where it calls the function twice with F(3) and F(2). F(3) and F(2) then each subsequently call the function again -- F(3) calls F(2) and F(1), and F(2) calls F(1) and F(0), as shown in the tree structure below (Figure 1). The F(1) and F(0) cases are the final, terminating cases in the tree and return the value of 1 or 0, respectively. So, just as Wikipedia said, the recursive case breaks down the problem to smaller instances, and it does that by allowing the user to define a function that calls itself: