title: python function to simplify fraction
body: <p>I am trying to write a function that will help me break down a fraction into simple components like so</p>
  
  <p><a href="https://i.stack.imgur.com/BWiPq.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BWiPq.jpg" alt="enter image description here"></a></p>
  
  <p>I wrote this function</p>
  
  <pre><code>from fractions import Fraction
  def lowest_fraction(frac):
      num = frac[0]
      den = frac[-1]
      if frac == (1, den):
          yield frac
      while frac != (1, den):
          new_num = num - num//2
          rem = num - new_num
          new_frac = Fraction(new_num, den)
          frac = (new_frac.numerator, new_frac.denominator)
          num = rem
          yield frac
  </code></pre>
  
  <p>I ran the below</p>
  
  <pre><code>for each in [(1, 2), (3, 4), (3, 8), (5, 8), (7, 8), (7, 16), (9, 32)]:
      print('{}: '.format(each))
      for k in lowest_fraction(each):
          print('\t{}'.format(k))
  </code></pre>
  
  <p>Here's the output</p>
  
  <pre><code>(1, 2): 
      (1, 2)
  (3, 4): 
      (1, 2)
      (1, 4)
  (3, 8): 
      (1, 4)
      (1, 8)
  (5, 8): 
      (3, 8)
      (1, 8)
  (7, 8): 
      (1, 2)
      (1, 4)
      (1, 8)
  (7, 16): 
      (1, 4)
      (1, 8)
      (1, 16)
  (9, 32): 
      (5, 32)
      (1, 16)
      (1, 32)
  </code></pre>
  
  <p>You can see that the output for <code>(3, 8)</code> and <code>(9, 32)</code> is not in their simplest form. I think what I want to do can be accomplished by writing a recursive code but I cannot presently write one because I don't fully grab the concept of recursion yet.</p>