This result is then returned to the previous instance of the fibonacci method in order to again help with the line of code’s resolution to actual values in that instance. The result is that the line of code: fibonacci(number - 1) + fibonacci(number - 2)Ĭan now be resolved by adding the two values. As each term is resolved to the value 0 or 1, the previous instance of the method can be resolved to an actual value. Each time a recursive call is made to the fibonacci method, the current state, or instance, of the method is stored in memory (the stack), and a new value is passed to the method for the next instance of the method to use. It may help to think in terms of the time dimension and different ‘instances’ of the fibonacci method here. This allows us to resolve f(2), which is f(1) + f(0) = 1. On the tree structure in the diagram, we have resolved f(0) = 0 and also f(1) = 1.
RECURSIVE SEQUENCE CALCULATOR CODE
There are no more recursion operations left to do as both terms in the line of code have been resolved to actual values:įibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
The same two lines of code above will result in a value of 0 (zero) when fibonacci(0) is evaluated. Ruby will store this value as the result of fibonacci(1), and continue to evaluate fibonacci(0). Hence, number is returned as can be seen in the 2nd line below (which will return 1 in this case). In Ruby the code do not have to read “return number”, it only needs to state the variable whose value is to be returned. It will get a result of 1 because of the two lines of code shown below, and with number = 1. In order to do the evaluation and make use of the fibonacci method, while the program is already currently inside the fibonacci method, the computer will store the current state or instance of the fibonacci method (we can call this instance ‘fibonacci(2)’ ), and then evaluate fibonacci(1). The computer will need to call the fibonacci method for each of these two terms. The next step is to find the values of the two terms, fibonacci(1) and fibonacci(0). Replace ‘ number’ with the value 2 and the line of code becomes: The following line of code is now about to be executed: fibonacci(number - 1) + fibonacci(number - 2) You can see from the method code that we end up in the ‘ else’ section of the ‘ if’ statement (as number = 2, which is not smaller than 2). We begin by feeding the fibonacci method the value of 2, as we want to calculate fibonacci(2). for finding the 2nd element in the Fibonacci sequence (we start counting at 0). This is the small tree for fibonacci(2), i.e. The ones that have f(2) and then under that f(1) and f(0). To start with, let’s also look at the tree structure in the diagram below:įor now, only look at the leftmost three blocks. # fibonacci.rb def fibonacci(number) if number < 2 number else fibonacci(number - 1) + fibonacci(number - 2) end end The exit condition here is the first part of the ‘ if’ statement and is met when the method variable number is smaller than 2. A method or function that calls itself until some exit condition is reached. The mind-twisting part (for those new to programming) comes in where the code inside the fibonacci() method calls itself not once but twice (3rd last line)! Even if you do not know Ruby at all, it should make some sense to you. In maths, the Fibonacci sequence is described as : the sequence of numbers where the first two numbers are 0 and 1, with each subsequent number being defined as the sum of the previous two numbers in the sequence.Ġ, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 and so on. I will attempt to explain how this method works using the code as well as a tree diagram as presented in the Launch School course.
During the section where we learn about recursion, the Fibonacci sequence is used to illustrate the concept.īelow is a recursive method, written in Ruby, to find the nth number in the Fibonacci sequence.
I am currently enrolled at Launch School in order to learn the art of programming.
0 kommentar(er)
