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.






Related Topics
  1. Python print statement "Syntax Error: invalid syntax"
  2. Installing Python Modules with pip
  3. How to get current date and time in Python?
  4. No module named 'pip'
  1. How to get the length of a string in Python
  2. ModuleNotFoundError: No module named 'sklearn'
  3. ModuleNotFoundError: No module named 'cv2'
  4. Python was not found; run without arguments
  5. Attempted relative import with no known parent package
  6. TypeError: only integer scalar arrays can be converted to a scalar index
  7. A value is trying to be set on a copy of a slice from a DataFrame
  8. ValueError: setting an array element with a sequence
  9. Indentationerror: unindent does not match any outer indentation level
  10. Valueerror: if using all scalar values, you must pass an index
  11. ImportError: libGL.so.1: cannot open shared object file: No such file or directory
  12. Python Try Except | Exception Handling
  13. Custom Exceptions in Python with Examples
  14. Python String replace() Method
  15. sqrt Python | Find the Square Root in Python
  16. Read JSON file using Python
  17. Binary search in Python
  18. Defaultdict in Python
  19. Int Object is Not Iterable – Python Error
  20. os.path.join in Python
  21. TypeError: int object is not subscriptable
  22. Python multiline comment
  23. Typeerror: str object is not callable
  24. Python reverse List
  25. zip() in Python for Parallel Iteration
  26. strftime() in Python
  27. Typeerror: int object is not callable
  28. Python List pop() Method
  29. Python any() function
  30. Python any() Vs all()
  31. Python pass Statement
  32. Python Lowercase - String lower() Method
  33. Modulenotfounderror: no module named istutils.cmd
  34. Append to dictionary in Python : Key/Value Pair
  35. timeit | Measure execution time of small code
  36. Python Decimal to Binary
  37. GET and POST requests using Python
  38. Difference between List VS Set in Python
  39. How to Build Word Cloud in Python?
  40. Binary to Decimal in Python
  41. Modulenotfounderror: no module named 'apt_pkg'
  42. Convert List to Array Python