![]() 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. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |