Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Fibonacci
#1
Hi Guys,

I am a Python beginner and trying to write a code for Fibonacci sequence.
I wrote the following code and got a following result: [1, 1, 3, 5, 8, 13, 21, 34, 55, 89]
I was expecting "2" to be included between second and third number...
Can anyone explain what is wrong with this code?
Thank you!
Yasunaga

def Fibo(n):
    a,b=1,1
    if n==0:
        return a
    elif n==1:
        return b
    else:
        for x in range (n):
            a,b = b, a+b
        return b
Fibonacci=list([Fibo(n) for n in range(0,10)])
print(Fibonacci)
Yoriz write May-15-2021, 11:28 AM:
Please post all code, output and errors (in their entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.
Reply
#2
a,b=1,1 has a wrong initial value.
The final return is returning the wrong thing.
Reply
#3
Also it dos not help to change initial values,when return return b change to return a.
Reply
#4
(May-15-2021, 11:51 AM)Yoriz Wrote: a,b=1,1 has a wrong initial value.
The final return is returning the wrong thing.

Hi Joriz,

thank you for your reply. Fibonacci can take any initial values. It just returns a third value adding first and second value. What I do not understand is
1. why third value is 3 as opposed to 2 (1+1)
2. why fourth value is 5? Why is it not an addition of 1 and 3 (previous two numbers)?
Reply
#5
Think about your logic as well. Your method of creating the list calculates the entire list up to n each time through the loop. So, to get a list of 10 values you generate the list to 3, list to 4, list to 5, etc. Not explaining this well, but if you put a
print('in loop')
after line 9 you will see what I mean. An efficient algorithm would only do this 8 times (excludes the first 2 entries).
Reply
#6
Oh, and have that print statement indented to the level of line 9
Reply
#7
(May-15-2021, 02:07 PM)jefsummers Wrote: Think about your logic as well. Your method of creating the list calculates the entire list up to n each time through the loop. So, to get a list of 10 values you generate the list to 3, list to 4, list to 5, etc. Not explaining this well, but if you put a
print('in loop')
after line 9 you will see what I mean. An efficient algorithm would only do this 8 times (excludes the first 2 entries).

Hi Jefsummers,

thank you for your comment! Thanks to that, I understood what was wrong.

Cheers,
Yasunaga
Reply
#8
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. Wink
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  fibonacci ***Time limit exceeded*** frequency 18 10,053 Nov-29-2018, 09:03 PM
Last Post: frequency
  Fibonacci sequence Darbandiman123 2 2,667 Sep-26-2018, 02:32 PM
Last Post: Darbandiman123
  Help debug my fibonacci implementation dineshpabbi10 6 3,923 May-16-2018, 12:12 PM
Last Post: dineshpabbi10
  Fibonacci Sequence on Turtle JRod 9 12,417 Feb-06-2017, 01:24 PM
Last Post: JRod

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020