Fibonacci sequence python8/16/2023 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. Next, we have a for loop similar to the loop in the fibLoop() function. Here, instead of using a and b to store the first two terms in the sequence, we use a list called fib. Let’s look at the last case (from lines 8 to 12). The first three cases should be quite self-explanatory. The difference is that we return a list instead of a single number. The code above is very similar to the fibLoop() function we wrote earlier. Since fibRec(2) and fibRec(1) are both base cases, they return the value 1 and 0 to the caller respectively.įibRec(3) then adds these two values (0 + 1 = 1) and returns the answer to its caller.įibRec(4) adds this value together with the value returned by fibRec(2) below and returns the result to the caller (line 11). When fibRec(4) calls fibRec(3), fibRec(3) in turn calls fibRec(2) and fibRec(1) (highlighted in orange above). Line 11 calls fibRec(4), which in turn calls fibRec(3) and fibRec(2). The diagram below shows what happens when we run line 11: On line 11, we call fibRec(4) and use the print() function to print its result. 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. Inside the function, we have three base cases from lines 2 to 7. On line 1, we define a function called fibRec() that has one parameter n. Notice how much more elegant this function is? To use recursion to find the n th term of a Fibonacci sequence, we can use the function below: The base cases include the cases where n is negative (return -1), n is 1 (return 0) and n is 2 (return 1). In the case of a Fibonacci sequence, we have multiple base cases. Similar to all other recursion problems, we need to have a base case that returns the result and stops the recursion. This makes it a perfect case for using recursion. In turn, we can find the 5 th term by finding the 4 th and 3 rd terms and so on. For instance, we can find the 6 th term by finding the 5 th and 4 th terms. In the case of a Fibonacci sequence, we can find the n th term of the sequence by finding the (n-1) th and (n-2) th terms. Using recursionīesides using a for loop to calculate the n th term of a Fibonacci sequence, we can use recursion.Īs mentioned in a previous post, recursion is very useful when a problem can be solved by solving smaller instances of the same problem. If you run the code above, you’ll get 34 as the output. We call the function on line 18 (passing 10 as the argument) and use the print() function to print the result. We then return this value using a return statement on line 16. Next, we update the values of a and b so that they store the values of the most recent two numbers.Īfter we finish iterating through the for loop, result stores the n th term of the sequence. Inside the for loop, we calculate the Fibonacci value for the i th term by adding a with b. (Recall that range(x, y) gives us the numbers from x to y-1, not x to y) Next, we have a for loop that loops from i = 3 to i = n. Adding a and b then gives us the 7 th term in the sequence.īesides a and b, we also declare a variable called result and initialize it to 0 (line 11). When the loop runs again the next time, i becomes 7. For instance, when i equals 6, a and b will be updated to store the 5 th and 6 th terms in the sequence. At present, a and b store the first and second terms in the sequence respectively.Īs 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. Inside the else case, we first assign 0 and 1 to the variables a and b respectively.Ī and b are used to store the preceding two numbers of any number in the sequence. If n is not negative, 0, 1 or 2, we move on to the else case (lines 8 to 16). If it is, we return the values 0 and 1 respectively. Next, we check if n is 1 (the first term) or 2 (the second term). Inside the function, we return -1 if n is invalid (i.e. For instance, if we want to find the 10 th term, n equals 10. Here, we first define a function called fibLoop() that has one parameter n.
0 Comments
Leave a Reply.AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |