Python Program to Find nth Fibonacci Number

You can find the nth Fibonacci number in Python by using a loop to add the two previous numbers starting from 0 and 1, like this: def fibonacci(n): a, b = 0, 1; for _ in range(n): a, b = b, a + b; return a.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the nth Fibonacci number, start with the first two numbers 0 and 1. Then, keep adding the last two numbers to get the next one until you reach the nth number. This way, you build the sequence step by step.

Algorithm

1

Get the input number n.

2

Initialize two variables to 0 and 1 for the first two Fibonacci numbers.

3

Repeat n times: update the two variables to the next pair in the sequence.

4

After the loop, the first variable holds the nth Fibonacci number.

5

Return this value.

Code

python

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

print(fibonacci(10))

Output

55

Dry Run

Let's trace fibonacci(5) through the code

1

Initialize

a = 0, b = 1

2

Iteration 1

a, b = 1, 1 (0+1)

3

Iteration 2

a, b = 1, 2 (1+1)

4

Iteration 3

a, b = 2, 3 (1+2)

5

Iteration 4

a, b = 3, 5 (2+3)

6

Iteration 5

a, b = 5, 8 (3+5)

7

Return

Return a = 5

Iteration	a	b
0	0	1
1	1	1
2	1	2
3	2	3
4	3	5
5	5	8

Why This Works

Step 1: Start with base numbers

We begin with a = 0 and b = 1 because the Fibonacci sequence starts with 0 and 1.

Step 2: Update numbers in loop

Each loop updates a to the current b, and b to the sum of old a and b, moving forward in the sequence.

Step 3: Return nth number

After repeating this process n times, a holds the nth Fibonacci number, which we return.

Alternative Approaches

Recursive approach

python

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

Simple but inefficient for large n due to repeated calculations.

Using memoization

python

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))

Faster than plain recursion by saving results but uses extra memory.

Using Binet's formula

python

import math

def fibonacci(n):
    phi = (1 + math.sqrt(5)) / 2
    return int(round((phi**n) / math.sqrt(5)))

print(fibonacci(10))

Uses a math formula for direct calculation but may have rounding errors for large n.

Complexity: O(n) time, O(1) space

Time Complexity

The iterative method loops n times, so it takes linear time O(n).

Space Complexity

Only a few variables are used, so space is constant O(1).

Which Approach is Fastest?

Iteration is fastest and uses least memory; recursion without memoization is slow; memoization uses extra space but speeds up recursion.

Approach	Time	Space	Best For
Iteration	O(n)	O(1)	Large n, efficient
Recursion	O(2^n)	O(n)	Small n, simple code
Memoization	O(n)	O(n)	Medium n, faster recursion
Binet's formula	O(1)	O(1)	Quick estimate, small rounding errors