Jamie, Author at Learn Coding Fast

In today's post, we'll look at two ways to calculate the nth term of a Fibonacci sequence in Python. We'll also work on a practice question that requires us to write a function to display the first n terms of the sequence. Here are some topics we'll be covering in today's post: What is the Fibonacci sequenceWhat is recursion2 ways to calculate the nth term of a Fibonacci sequence in Python Key Concepts Let's first discuss some key concepts needed for today's practice question. What is the Fibonacci sequence? The Fibonacci sequence is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The first 10 terms of the Fibonacci sequence are shown below: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 By definition, the first two numbers of a Fibonacci sequence are 0 and 1. To get the third number, we add the first two numbers. Hence, we get 0 + 1 = 1 as the third number. To get the fourth number, we add the second and third numbers. Hence, we get 1 + 1 = 2 as the fourth number. We keep repeating this process until we get all 10 terms of the sequence. How to use Python to get the nth term of a Fibonacci sequence? There are two ways to get the nth term of a Fibonacci sequence using Python. The first way is to use a loopThe second way is to use recursion Let's look at each of them. Using a loop Suppose we want to get the 10th term of a Fibonacci sequence. From the previous section, we know that the 10th term is 34. To calculate it using Python, we can use the code below: def fibLoop(n): if n <= 0: return -1 elif n == 1: return 0 elif n == 2: return 1 else: a = 0 b = 1 result = 0 for i in range(3, n+1): result = a + b a = b b = result return result print(fibLoop(10)) Here, we first define a function called fibLoop() that has one parameter n. n represents the term number. For instance, if we want to find the 10th term, n equals 10. Inside the function, we return -1 if n is invalid (i.e. if n <= 0). Next, we check if n is 1 (the first term) or 2 (the second term). If it is, we return the values 0 and 1 respectively. If n is not negative, 0, 1 or 2, we move on to the else case (lines 8 to 16). Inside the else case, we first assign 0 and 1 to the variables a and b respectively. a and b are used to store the preceding two numbers of any number in the sequence. At present, a and b store the first and second terms in the sequence respectively. As we iterate through the for loop later, a and b will be updated to store the preceding two numbers of subsequent numbers in the sequence. For instance, when i equals 6, a and b will be updated to store the 5th and 6th terms in the sequence. When the loop runs again the next time, i becomes 7. Adding a and b then gives us the 7th term in the sequence. Besides a and b, we also declare a variable called result and initialize it to 0 (line 11). Next, we have a for loop that loops from i = 3 to i = n. (Recall that range(x, y) gives us the numbers from x to y-1, not x to y) Inside the for loop, we calculate the Fibonacci value for the ith term by adding a with b. Next, we update the values of a and b so that they store the values of the most recent two numbers. After we finish iterating through the for loop, result stores the nth term of the sequence. We then return this value using a return statement on line 16. With that, the function is complete. We call the function on line 18 (passing 10 as the argument) and use the print() function to print the result. If you run the code above, you'll get 34 as the output. Using recursion Besides using a for loop to calculate the nth term of a Fibonacci sequence, we can use recursion. As mentioned in a previous post, recursion is very useful when a problem can be solved by solving smaller instances of the same problem. In the case of a Fibonacci sequence, we can find the nth term of the sequence by finding the (n-1)th and (n-2)th terms. For instance, we can find the 6th term by finding the 5th and 4th terms. In turn, we can find the 5th term by finding the 4th and 3rd terms and so on. This makes it a perfect case for using recursion. Similar to all other recursion problems, we need to have a base case that returns the result and stops the recursion. In the case of a Fibonacci sequence, we have multiple base cases. The base cases include the cases where n is negative (return -1), n is 1 (return 0) and n is 2 (return 1). To use recursion to find the nth term of a Fibonacci sequence, we can use the function below: def fibRec(n): if n <= 0: return -1 elif n == 1: return 0 elif n == 2: return 1 else: return fibRec(n-1) + fibRec(n-2) print(fibRec(4)) Notice how much more elegant this function is? On line 1, we define a function called fibRec() that has one parameter n. Inside the function, we have three base cases from lines 2 to 7. On lines 8 and 9, we have the recursive case where we call fibRec(n-1) and fibRec(n-2) and return the result of their sum. On line 11, we call fibRec(4) and use the print() function to print its result. The diagram below shows what happens when we run line 11: Line 11 calls fibRec(4), which in turn calls fibRec(3) and fibRec(2). When fibRec(4) calls fibRec(3), fibRec(3) in turn calls fibRec(2) and fibRec(1) (highlighted in orange above). Since fibRec(2) and fibRec(1) are both base cases, they return the value 1 and 0 to the caller respectively. fibRec(3) then adds these two values (0 + 1 = 1) and returns the answer to its caller. fibRec(4) adds this value together with the value returned by fibRec(2) below and returns the result to the caller (line 11). If you run the code above, you'll get 2 as the output. Got it? Practice Question Good! Now that we know how to get the nth term of a Fibonacci sequence, let's work on today's practice question. The practice question for today requires us to write a function called fibSequence() that has one parameter n. This function returns an empty list if n is smaller than 1. Else, it returns a list containing the terms of a Fibonacci sequence up to the nth term. You can assume that n is an integer. Expected Results To test your function, you can use the statements below: print(fibSequence(-1)) print(fibSequence(2)) print(fibSequence(6)) print(fibSequence(10)) You should get the following output: [] [0, 1] [0, 1, 1, 2, 3, 5] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] Suggested Solutions Click to see the suggested solutions Solution 1 def fibSequence(n): if n <= 0: return [] elif n == 1: return [0] elif n == 2: return [0, 1] else: fib = [0, 1] for i in range(2, n): fib.append(fib[i-2] + fib[i-1]) return fib The code above is very similar to the fibLoop() function we wrote earlier. The difference is that we return a list instead of a single number. The first three cases should be quite self-explanatory. Let's look at the last case (from lines 8 to 12). Here, instead of using a and b to store the first two terms in the sequence, we use a list called fib. Next, we have a for loop similar to the loop in the fibLoop() function. Inside the for loop, instead of using a and b to access the preceding two terms of the sequence, we access them using the indexes of the fib list. For instance, when i equals 2, fib[i-2] and fib[i-1] give us fib[0] and fib[1] respectively (recall that indexes of lists start from 0). These two values represent the first and second terms in the Fibonacci sequence. We add the two values and append the result to the fib list. This gives us fib[2], which represents the 3rd term in the Fibonacci sequence. This continues until we get all the n terms in the Fibonacci sequence. When that happens (after the for loop ends), we return the fib list. With that, the function is complete. Solution 2 In addition to using a for loop to get the terms of a Fibonacci sequence, we can the recursion technique discussed previously. This is how we do it: def fibRec(n): if n <= 0: return -1 elif n == 1: return 0 elif n == 2: return 1 else: return fibRec(n-1) + fibRec(n-2) def fibSequence(n): result = [] for i in range(1, n+1): result.append(fibRec(i)) return result We've covered the fibRec() function in the previous section on recursion. After the fibRec() function, we define another function called fibSequence() function that has one parameter n. Inside the function, we first initialize an empty list called result. Next, we use a for loop to iterate from i = 1 to i = n. Inside the for loop, we call the fibRec() function to find the ith term of the Fibonacci sequence and append the result to result. Finally, we return the result list on line 15. With that, the function is complete. That's it. Hope you find today's post useful.