Python Program for n-th Fibonacci number

Python Program for n-th Fibonacci Number

The Fibonacci sequence is one of the most commonly used examples for understanding programming concepts such as recursion, loops, arrays, and dynamic programming. In this sequence, every number is calculated by adding the two numbers that come before it.

The sequence starts with 0 and 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

For example:

• The first two values are 0 and 1.
• The third value is 0 + 1 = 1.
• The fourth value is 1 + 1 = 2.
• The fifth value is 1 + 2 = 3.
• The sixth value is 2 + 3 = 5.

The Fibonacci sequence can be mathematically represented using the following recurrence relation:

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

The starting values are:

F(0) = 0
F(1) = 1

There are multiple ways to find the n-th Fibonacci number in Python. In this tutorial, we will explore recursion, dynamic programming, space optimization, and arrays.

1. Finding n-th Fibonacci Number Using Recursion

Recursion is a programming technique in which a function calls itself to solve smaller versions of the same problem. Fibonacci numbers are a common example because every number depends on the previous two numbers.

Python Example

# Function to calculate the nth Fibonacci number
def Fibonacci_Series(n):
    if n < 0:
        print("Invalid input! Fibonacci numbers are only defined for non-negative integers.")
        return None
    elif n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci_Series(n - 1) + Fibonacci_Series(n - 2)

# Testing the function
print("12th Fibonacci Number:", Fibonacci_Series(12))

Output

12th Fibonacci Number: 144

Explanation

The Fibonacci_Series() function uses three main conditions. If the value of n is negative, the input is considered invalid. When n is 0, the function returns 0, and when n is 1, it returns 1.

For values greater than 1, the function calls itself twice and adds the results:

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

This method is simple and closely follows the mathematical definition of Fibonacci numbers. However, basic recursion repeats many calculations, making it inefficient for larger values of n.

2. Finding n-th Fibonacci Number Using Dynamic Programming

Dynamic programming can make the Fibonacci calculation more efficient by storing values that have already been calculated. This avoids calculating the same Fibonacci number repeatedly.

Python Example

# Dynamic programming function
def Fibonacci_series(n):
    if n < 0:
        print("Invalid input!")
        return None
    elif n == 0:
        return 0
    elif n == 1:
        return 1

    fib_array = [0, 1]

    for i in range(2, n + 1):
        fib_array.append(fib_array[i - 1] + fib_array[i - 2])

    return fib_array[n]

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output

12th Fibonacci Number: 144

Explanation

The program begins with a list containing the first two Fibonacci numbers:

[0, 1]

The for loop starts from index 2. At every iteration, the program adds the two previous values and stores the result in the list.

fib_array[i] = fib_array[i - 1] + fib_array[i - 2]

After the required position has been calculated, fib_array[n] returns the n-th Fibonacci number.

3. Dynamic Programming with Space Optimization

The previous dynamic programming method stores the complete sequence in an array. However, if we only need the n-th Fibonacci number, storing every value is unnecessary.

Only the previous two Fibonacci values are required to calculate the next value. Therefore, two variables can be used to reduce memory usage.

Python Example

# Function to calculate the nth Fibonacci number
# using space optimization
def Fibonacci_series(n):
    if n < 0:
        print("Invalid input!")
        return None
    elif n == 0:
        return 0
    elif n == 1:
        return 1

    prev1, prev2 = 0, 1

    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev1, prev2 = prev2, current

    return prev2

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output

12th Fibonacci Number: 144

Explanation

The variables prev1 and prev2 keep track of the previous two Fibonacci values. The next number is calculated using:

current = prev1 + prev2

The variables are then updated:

prev1, prev2 = prev2, current

This process continues until the n-th value is reached. Because only two values are stored, this approach requires less memory than storing the complete Fibonacci sequence.

4. Finding n-th Fibonacci Number Using Arrays

Another approach is to create an array that stores all Fibonacci numbers from F(0) to F(n). This is useful when you need access to the complete sequence.

Python Example

# Function to calculate the nth Fibonacci number using an array
def Fibonacci_series(n):
    if n < 0:
        print("Invalid input!")
        return None
    elif n == 0:
        return 0
    elif n == 1:
        return 1

    # Create an array to store Fibonacci numbers
    fib_array = [0] * (n + 1)
    fib_array[1] = 1

    for i in range(2, n + 1):
        fib_array[i] = fib_array[i - 1] + fib_array[i - 2]

    return fib_array[n]

# Testing the function
print("12th Fibonacci Number:", Fibonacci_series(12))

Output

12th Fibonacci Number: 144

Explanation

The statement below creates an array with n + 1 positions:

fib_array = [0] * (n + 1)

The first Fibonacci value is already represented by the initial zeros, while the second value is explicitly set to 1:

fib_array[1] = 1

The loop calculates each remaining value using the two preceding elements:

fib_array[i] = fib_array[i - 1] + fib_array[i - 2]

Finally, fib_array[n] provides the required Fibonacci number.

Comparison of Fibonacci Methods

Method	Approach	Memory Usage
Recursion	Uses repeated function calls	Higher due to repeated calculations
Dynamic Programming	Stores calculated Fibonacci values	O(n)
Space Optimization	Stores only the previous two values	O(1)
Arrays	Stores the complete sequence	O(n)

Complete Advance AI Topics: Click Here
SQL Tutorial: Click Here
YT:- DecodeIT

Frequently Asked Questions

1. What is the Fibonacci sequence in Python?

The Fibonacci sequence is a series where every number is calculated by adding the two preceding numbers. It begins with 0 and 1.

2. What is the formula for the n-th Fibonacci number?

The recurrence relation is F(n) = F(n - 1) + F(n - 2), with F(0) = 0 and F(1) = 1.

3. What is the 12th Fibonacci number?

Using zero-based Fibonacci indexing, where F(0) = 0 and F(1) = 1, F(12) is 144.

4. Why can recursion be inefficient?

Basic recursive Fibonacci calculations repeatedly calculate the same smaller values, which can make the program inefficient for large inputs.

5. What is dynamic programming in Fibonacci?

Dynamic programming stores previously calculated Fibonacci values so that the program does not need to calculate the same values again.

6. Which method uses the least additional memory?

The space-optimized method uses only two variables for the previous Fibonacci values, giving it constant additional space usage.

7. Can a for loop be used to calculate Fibonacci numbers?

Yes. A for loop can repeatedly calculate the next Fibonacci number by adding the two previous values.

8. Why use an array for Fibonacci numbers?

An array is useful when you need to store and access the complete Fibonacci sequence from the beginning through the n-th value.

Conclusion

Finding the n-th Fibonacci number in Python is a useful programming exercise for understanding several important concepts. The recursive method follows the mathematical definition directly, while dynamic programming avoids unnecessary repeated calculations. Space optimization further reduces memory usage by keeping only the two values required for the next calculation. An array-based approach is useful when the complete sequence needs to be stored.

By practicing these four approaches, you can understand how the same problem can be solved using different programming techniques and how memory and calculation efficiency can vary between implementations.

Keywords: Python Program for n-th Fibonacci number, fibonacci series in Python, Python Program for n-th Fibonacci Number,Python Program for n-th Fibonacci Number,Python Program for n-th Fibonacci Numberfibonacci series program in Python using for loop, fibonacci series using recursion in Python, nth Fibonacci number formula,Python Program for n-th Fibonacci Number,Python Program for n-th Fibonacci NumberPython Program for n-th Fibonacci Number,Python Program for n-th Fibonacci Number,Python Program for n-th Fibonacci Number,Python Program for n-th Fibonacci Number Python program for Fibonacci series, Python program for n-th Fibonacci number with code, Fibonacci number using dynamic programming, Python Program for n-th Fibonacci Number