51 lines
1.6 KiB
Python
51 lines
1.6 KiB
Python
# Code-A1 (Fibonacci)
|
|
# Problem Statement: Write a program non-recursive and recursive program to calculate Fibonacci numbers and analyze their time and space complexity.
|
|
|
|
# Initalize global variables
|
|
iteration_counter = 0
|
|
recursion_counter = 0
|
|
|
|
# Iteration
|
|
def fibonacci_iteration(n):
|
|
fib_series = [] # For storing Fibonacci series
|
|
previous = 0 # Previous
|
|
current = 1 # Next
|
|
global iteration_counter # Global iteration counter
|
|
iteration_counter = 0 # Initialize global iteration counter to 0
|
|
|
|
for i in range(n):
|
|
fib_series.append(previous)
|
|
previous, current = current, previous + current
|
|
iteration_counter += 1
|
|
|
|
return fib_series
|
|
|
|
# Recursion
|
|
def fibonacci_recursion(n):
|
|
global recursion_counter # Global recursion counter
|
|
recursion_counter += 1 # Increment recursion counter for each call
|
|
|
|
if (n <= 0): # Handle n less than or equal to 0
|
|
return 0
|
|
elif (n <= 1): # Handle n less than or equal to 1
|
|
return n
|
|
else: # Recursive call
|
|
return fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2)
|
|
|
|
n = int(input("Enter total numbers to print in fibonacci series:\t"))
|
|
|
|
# Fibonacci using iteration
|
|
fib_series = fibonacci_iteration(n)
|
|
print(f"Fibonacci using iteration:\t{fib_series}")
|
|
print(f"Iteration counter:\t{iteration_counter}| Time Complexity: O(n) (linear growth)")
|
|
|
|
print("="*80)
|
|
|
|
# Fibonacci using recursion
|
|
fib_series = []
|
|
for i in range(n):
|
|
fib_series.append(fibonacci_recursion(i))
|
|
print(f"Fibonacci using recursion:\t{fib_series}")
|
|
print(f"Recursion counter:\t{recursion_counter} | Time Complexity: O(2^n) (exponential growth)")
|
|
|