Fibonacci sequence in Python

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. In other words, each number in the series is the sum of the previous two numbers.


The sequence starts as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, ...

As you can see, each number is the sum of the two preceding ones. For example, 1+1=2, 2+1=3, 3+2=5, and so on. The Fibonacci series has many interesting mathematical properties and occurs frequently in nature and in various fields of study, such as mathematics, biology, and economics.

Fibonacci series using recursion

Following an example of a recursive function to generate the Fibonacci sequence in Python (not using any loop):

def fibonacci(n): if n <= 0: return [] elif n == 1: return [0] elif n == 2: return [0, 1] else: fib_list = fibonacci(n-1) fib_list.append(fib_list[-1] + fib_list[-2]) return fib_list print(fibonacci(10))
#Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Above function uses recursion to calculate the nth number in the Fibonacci sequence by summing the previous two numbers.

Fibonacci series using Dynamic Programming

Following is an example of a function to generate the Fibonacci series using dynamic programming in Python:

def fibonacci(n): if n <= 1: return n else: fib = [0, 1] for i in range(2, n+1): fib.append(fib[-1] + fib[-2]) print(fib[-1]) return fib[-1] fibonacci(10)
#Output: 1 2 3 5 8 13 21 34 55

Above function uses dynamic programming to avoid redundant calculations by storing previously computed Fibonacci numbers in a list and reusing them as needed.

Time complexity:

The time complexity of this function is O(n), which is linear. This is because the function iterates n-1 times using the for loop to compute the nth Fibonacci number, and each iteration requires only constant time operations to access and update the list of previously computed numbers.

Space complexity

The space complexity of this function is O(n), which is linear. This is because the function creates a list of length n+1 to store the previously computed Fibonacci numbers. The space used by the list grows linearly with the input size n. However, we could improve the space complexity by only storing the last two Fibonacci numbers instead of the entire sequence. This would reduce the space complexity to O(1).

Fibonacci series using Space Optimized

Following is an example of a space-optimized function to generate the Fibonacci sequence in Python:

def fibonacci(n): if n <= 1: return n else: a, b = 0, 1 for i in range(2, n+1): c = a + b a, b = b, c print(b) return b fibonacci(10)
#Output: 1 2 3 5 8 13 21 34 55

Above function is the same as the for loop version provided earlier, but it uses only two variables (a and b) to keep track of the previous two Fibonacci numbers instead of a list.

Time complexity:

The time complexity of this function is O(n), which is linear. This is because the function iterates n-1 times using the for loop to compute the nth Fibonacci number.

Space complexity

The space complexity of this function is O(1), which is constant. This is because the function only uses two variables (a and b) to keep track of the previous two Fibonacci numbers, and the space used by the variables does not depend on the input size n. This is the most space-efficient way to compute the Fibonacci sequence, using constant space.

Fibonacci series using while loop

Following is an example of a function to generate the Fibonacci sequence using a while loop in Python (not using recursion):

def fibonacci(n): if n <= 1: return n else: a, b = 0, 1 i = 2 while i <= n: c = a + b a, b = b, c i += 1 print(b) return b fibonacci(10)
#Output: 1 2 3 5 8 13 21 34 55

Above function iteratively calculates the nth number in the Fibonacci sequence by adding the previous two numbers using a while loop.

Time complexity:

The time complexity of this function is O(n), which is linear. This is because the function iterates n-1 times using the while loop to compute the nth Fibonacci number.

Space complexity

The space complexity of this function is O(1), which is constant. This is because the function only uses three variables (a, b, and c) to keep track of the previous two Fibonacci numbers and the current Fibonacci number. The space used by the variables does not depend on the input size n.

Fibonacci series using Backtracking

Backtracking is not typically used to generate the Fibonacci sequence, as it is not an efficient approach for this particular problem. However, in theory, you could use backtracking to generate the Fibonacci sequence by exploring all possible combinations of Fibonacci numbers until you find the nth number.

Therefore, while it is possible to use backtracking to generate the Fibonacci sequence, it is not a practical or efficient approach for this problem.