File size: 2,141 Bytes
99a41ea |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
"""
Fibonacci computation functions for testing function analysis.
"""
def fibonacci_recursive(n):
"""Calculate fibonacci number using recursion."""
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
def fibonacci_iterative(n):
"""Calculate fibonacci number using iteration."""
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
def fibonacci_memoized(n, memo=None):
"""Calculate fibonacci number using memoization."""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
return n
memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
return memo[n]
def fibonacci_sequence(count):
"""Generate a sequence of fibonacci numbers."""
sequence = []
for i in range(count):
sequence.append(fibonacci_iterative(i))
return sequence
def compare_fibonacci_methods(n):
"""Compare different fibonacci calculation methods."""
import time
methods = [
("Recursive", fibonacci_recursive),
("Iterative", fibonacci_iterative),
("Memoized", fibonacci_memoized)
]
results = {}
for name, func in methods:
start_time = time.time()
result = func(n)
end_time = time.time()
results[name] = {
'result': result,
'time': end_time - start_time
}
return results
def validate_fibonacci_result(n, result):
"""Validate if a fibonacci result is correct."""
if n <= 1:
return result == n
# Use iterative method as baseline for validation
expected = fibonacci_iterative(n)
return result == expected
if __name__ == "__main__":
n = 10
print(f"Fibonacci({n}) using different methods:")
results = compare_fibonacci_methods(n)
for method, data in results.items():
print(f"{method}: {data['result']} (took {data['time']:.6f} seconds)")
print(f"\nFirst 15 fibonacci numbers: {fibonacci_sequence(15)}")
|