Beautified code to adhere to PEP8 standards, and added clarifying comment

franklindyer · franklindyer · commit b11cac749aa8 · 2020-07-08T22:20:33.000Z
diff --git a/algorithms/math/recursive_fibonacci.py b/algorithms/math/recursive_fibonacci.py
@@ -1,11 +1,8 @@
 """
     Recursivly compute the Fibonacci sequence using two different methods
-    main() compares the amount of time taken by each algorithm
     rec_fib(n) requires O(Fibo(n)) operations, whereas binary_rec_fib(n) requires less than O(n) 
 """
 
-import time
-
 def rec_fib(n):
     if n == 1:
         return 1
@@ -20,13 +17,16 @@ def binary_rec_fib(n):
     elif n == 0:
         return 0
     else:
+        # This recursive step takes advantage of the following two properties of the fibonacci numbers:
+        # Fibo(2n) = Fibo(n+1)^2 + Fibo(n)^2
+        # Fibo(2n+1) = Fibo(n+1)^2 - Fibo(n-1)^2
         sgn = n % 2
-        return binary_rec_fib((n-sgn)/2+1)**2 - ((-1)**sgn)*binary_rec_fib((n+sgn)/2-1)**2
+        return binary_rec_fib((n-sgn)/2 + 1)**2 - ((-1)**sgn) * binary_rec_fib((n+sgn)/2 - 1)**2
 
 def main():
     times = []
     n : int = int(input("n := "))
-    for i in range(0,n):
+    for i in range(0, n):
         print(binary_rec_fib(i))
 
 if __name__ == "__main__":
