Day 25：递归求斐波那契数列前 N 项

import time
from functools import lru_cache

class Solution:
  def __init__(self):
      self.temp = {}

  def fib_without_cache(self, n):
      if n == 1:
          return 1
      elif n == 2:
          return 1
      else:
          return self.fib_without_cache(n-1) + self.fib_without_cache(n-2)

  @lru_cache()
  def fib_with_lru_cache(self, n):
      if n == 1:
          return 1
      elif n == 2:
          return 1
      else:
          return self.fib_with_lru_cache(n-1) + self.fib_with_lru_cache(n-2)

  def fib_with_cache(self, n):
      if n == 1:
          return 1
      elif n == 2:
          return 1
      else:
          if n in self.temp:
              return self.temp[n]
          else:
              self.temp[n] = self.fib_with_cache(n-1) + self.fib_with_cache(n-2)
      return self.temp[n]

  def time_elasped(self,fun,i):
      start = time.time()
      print([fun(i) for i in range(1,32)])
      end = time.time()
      print(f'{fun} Time elasped: {end-start}')


s = Solution()

print('*'*40)
s.time_elasped(s.fib_without_cache,32)

print('*'*40)
s.time_elasped(s.fib_with_lru_cache,32)

print('*'*40)
s.time_elasped(s.fib_with_cache,32)