How to find the nth value in a Fibonacci series?

Question

# Function for nth Fibonacci number 

def Fibonacci(n): 
    if n<0: 
        print("Incorrect input") 
    # First Fibonacci number is 0 
    elif n==1: 
        return 0
    # Second Fibonacci number is 1 
    elif n==2: 
        return 1
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2) 

# Driver Program 

print(Fibonacci(9))

I am new to programming. I cant get how this codes finds out the Fibonacci number.... How does the program calculates the value of (n-1) and (n-2)

score 1 · Answer 1 · answered Jun 28 '20 at 11:15

1

Your program uses recursion.

Here you can find visualization, which could help you with understanding: https://observablehq.com/@victormutai/visualizing-recursive-fibonacci-algorithm

Alternative implementation is iterative algorithm. I could be easier to understand

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a

answered Jun 28 '20 at 11:15

xszym

928
1
5
11

Can you tell me something about how recursion works.. – Saurabh Jaisinghani Jun 29 '20 at 07:37

score 1 · Answer 2 · answered Jun 28 '20 at 11:28

Here is an illustratory diagram from the SICP book.

When Fibonacci(5) is invoked, Fibonacci(5-1) (fib 4) and Fibonacci(5-2) (fib 3) are invoked in return. When Fibonacci(4) is invoked, Fibonacci(4-1) and Fibonacci(4-2) are invoked in return, so on and so forth. This is called a recursion.

Finally, when either Fibonacci(2) or Fibonacci(1) is invoked, its result 1 and 0 is returned directly without further invocation. It is the termination conditions of such recursion.

By the way, as is depicted in the diagram, the multiple times' invocations of fib 3, which is seen as repeated calculation, result in inefficiency. So it is only for demonstrating how recursion works while usually not used to calculate fibs in practice.

score 0 · Answer 3 · answered Jun 28 '20 at 11:13

0

return Fibonacci(n-1)+Fibonacci(n-2)

This is a recursion. You should cache values to reduce recalculation.

moreover, there is Binet's formula to calculate it at O(1) time. https://en.wikipedia.org/wiki/Fibonacci_number

answered Jun 28 '20 at 11:13

Oleg Cherednik

17,377
4
21
35

score 0 · Answer 4 · answered Jun 28 '20 at 11:16

0

The idea behind that piece of code is recursion. Have a look at this to find out more about it.

answered Jun 28 '20 at 11:16

jvieira88

115
7

score 0 · Answer 5 · answered Jun 28 '20 at 11:27

To explain how your code works to identify the nth number in the Fibonacci series, first you need to understand how a Fibonacci series is generated.

0, 1, 1, 2, 3, 5, 8, 13, and so on.

Here if you look at the first two numbers it is 0 and 1, these are the base numbers, from there on the next number is found out by the addition of the previous two numbers. Hence the formula.

F(1) = 0
F(2) = 1
F(n) = F(n-1) + F(n-2)

Now if you look at your code the above is exactly depicted here. Any value of n less that 1 will be considered as invalid. A value of 1 returns a 0 and a value of 2 returns a 1. this is exactly the same as we have mentioned above.

Fibonacci(n-1)+Fibonacci(n-2)

Finally for all other cases we find the previous two numbers in the series by using the same rule(function) and sum them to get the desired number.

How to find the nth value in a Fibonacci series?

5 Answers5