This kind of problem can be solved in one of two ways: with recursion or with an iteration.
Recursion is "a method of solving a problem where the solution depends on solutions to smaller instances of the same problem" (
https://en.wikipedia.org/wiki/Recursion_...r_science). In the case of the Fibonacci sequence, it means that Fib(n) = Fib(n -1) + Fib(n - 2); notice how the solution to n depends on the solutions to n-1 and n-2, and the solutions to these can be expressed in the same way. Which brings us to an important point: a break point must be defined, where the equation must return a concrete value instead of continuing to "call itself." And in this case, the break point is defined as Fib(n) = n if n < 2 (Fib(0) = 0, and Fib(1) = 1).
Iteration basically is the use of a loop, and in this case you keep track of the values you need in order to build the solution from the ground up (which is the method you apply in your solution). You start with the cases that give you a concrete value and start calculating the next solutions until you reach the final value.
Both approaches have their advantages and disadvantages, and what you pick will usually depend on your specific needs. Recursion has the advantage of providing you with a simpler implementation of the solution, but it will consume more memory since every function call has a toll on memory use; also, the higher the number of recursive calls the longer the solution may take. An iterative approach, on the other hand, will consume less memory and run faster, but it may be more complex to implement and thus you may be more prone to errors.
Now, since the issues with your code have already been pointed out, I'm sharing code using both approaches explained above.
def fib(n):
if n < 2:
return n
else:
return fib(n - 2) + fib(n - 1)
def iter_fib(n):
sequence = []
for x in range(n):
if x < 2:
sequence.append(x)
else:
sequence.append(sequence[x - 2] + sequence[x - 1])
return sequence
if __name__ == '__main__':
print([fib(n) for n in range(11)])
print(iter_fib(11))Notice how the recursive solution is clear and simple. The function returns the Fibonacci of a given number, and then we just use a list comprehension to print a list of Fibonaccis from 0 to n-1 (by the way, the
list() in your
print() is not needed, as list comprehensions return a list). This, however, has the disadvantage that we will be calculating values over and over because we calculate the Fibonacci of every number one by one.
The iterative solution is also simple in this case, since we're making use of the values we've already appended to the sequence list to calculate the next one. So in this case, we're not returning the Fibonacci of n, but the Fibonacci *sequence* and thus we don't need to build it when printing.
If you have any doubts, feel free to ask.
Also, should any of these functions be modified to properly handle a negative integer? You might want to test them.
