# Python program to find the nth Fibonacci Number

Sure! Here’s a Python program to find the nth Fibonacci number:

```def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)

n = int(input("Enter the value of n: "))
print("The", n, "th Fibonacci number is:", fibonacci(n))
```

Here’s how the program works:

• The function `fibonacci(n)` takes an integer `n` as input and returns the nth Fibonacci number.
• The first three `if` statements handle special cases (n <= 0, n = 1, and n = 2) that have specific outputs.
• If n is greater than 2, the function uses recursion to calculate the nth Fibonacci number by adding the previous two Fibonacci numbers.
• Finally, the program prompts the user to enter the value of n, calls the `fibonacci()` function, and prints the result.

Note that this program assumes that the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, … If you want to start with a different sequence, you can adjust the special cases in the `fibonacci()` function accordingly.

### Finding nth Fibonacci Number using Recursion:

Certainly! Here’s a recursive Python program to find the nth Fibonacci number:

```def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)

n = int(input("Enter the value of n: "))
print("The", n, "th Fibonacci number is:", fibonacci(n))
```

Here’s how the program works:

• The function `fibonacci(n)` takes an integer `n` as input and returns the nth Fibonacci number.
• The first three `if` statements handle special cases (n <= 0, n = 1, and n = 2) that have specific outputs.
• If n is greater than 2, the function uses recursion to calculate the nth Fibonacci number by adding the previous two Fibonacci numbers.
• Finally, the program prompts the user to enter the value of n, calls the `fibonacci()` function, and prints the result.

Note that this program assumes that the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, … If you want to start with a different sequence, you can adjust the special cases in the `fibonacci()` function accordingly.

### Finding the nth Fibonacci Number using Dynamic Programming:

Sure! Here’s a Python program to find the nth Fibonacci number using dynamic programming:

```def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
fib = [0, 1]
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib[n-1]

n = int(input("Enter the value of n: "))
print("The", n, "th Fibonacci number is:", fibonacci(n))
```

Here’s how the program works:

• The function `fibonacci(n)` takes an integer `n` as input and returns the nth Fibonacci number.
• The first three `if` statements handle special cases (n <= 0, n = 1, and n = 2) that have specific outputs.
• If n is greater than 2, the function creates a list `fib` with the first two Fibonacci numbers (0 and 1).
• It then uses a loop to calculate the remaining Fibonacci numbers up to the nth number by adding the previous two Fibonacci numbers.
• Finally, the program prompts the user to enter the value of n, calls the `fibonacci()` function, and prints the result.

Note that this program uses dynamic programming to optimize the calculation of Fibonacci numbers by storing the previous Fibonacci numbers in a list instead of recalculating them every time. This reduces the time complexity from exponential to linear.

### Finding the nth Fibonacci Number using Dynamic Programming and Space Optimization:

Sure! Here’s a Python program to find the nth Fibonacci number using dynamic programming and space optimization:

```def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
a, b = 0, 1
for i in range(2, n):
a, b = b, a + b
return b

n = int(input("Enter the value of n: "))
print("The", n, "th Fibonacci number is:", fibonacci(n))
```

Here’s how the program works:

• The function `fibonacci(n)` takes an integer `n` as input and returns the nth Fibonacci number.
• The first three `if` statements handle special cases (n <= 0, n = 1, and n = 2) that have specific outputs.
• If n is greater than 2, the function initializes two variables `a` and `b` to the first two Fibonacci numbers (0 and 1).
• It then uses a loop to calculate the remaining Fibonacci numbers up to the nth number by adding `a` and `b` and swapping the values of `a` and `b` at each iteration.
• Finally, the program prompts the user to enter the value of n, calls the `fibonacci()` function, and prints the result.

Note that this program uses dynamic programming and space optimization to further optimize the calculation of Fibonacci numbers by storing only the previous two Fibonacci numbers in variables instead of a list. This reduces the space complexity from linear to constant.

### Finding the nth Fibonacci Number using Array:

Certainly! Here’s a Python program to find the nth Fibonacci number using an array:

```def fibonacci(n):
if n <= 0:
return "Invalid input"
elif n == 1:
return 0
elif n == 2:
return 1
else:
fib = [0] * n
fib[0] = 0
fib[1] = 1
for i in range(2, n):
fib[i] = fib[i-1] + fib[i-2]
return fib[n-1]

n = int(input("Enter the value of n: "))
print("The", n, "th Fibonacci number is:", fibonacci(n))
```

Here’s how the program works:

• The function `fibonacci(n)` takes an integer `n` as input and returns the nth Fibonacci number.
• The first three `if` statements handle special cases (n <= 0, n = 1, and n = 2) that have specific outputs.
• If n is greater than 2, the function creates a list `fib` of size `n` with all elements initialized to 0.
• It then assigns the first two Fibonacci numbers (0 and 1) to `fib[0]` and `fib[1]`.
• It then uses a loop to calculate the remaining Fibonacci numbers up to the nth number by adding the previous two Fibonacci numbers and storing the result in `fib[i]`.
• Finally, the program prompts the user to enter the value of n, calls the `fibonacci()` function, and prints the result.

Note that this program uses an array to store the Fibonacci numbers, which can be more memory efficient than using a list. However, this program has a space complexity of O(n) because it creates an array of size n.