title: Is is possible to move from (a,b) to (c,d)
body: <p>The problem was to output whether it is possible to move from a given point <code>(a,b)</code> to target <code>(c,d)</code></p>
  
  <p>We are restricted to positive co-ordinates only</p>
  
  <p>The following two moves are possible</p>
  
  <pre><code>(a,b) -&gt; (a+b,b)
  (a,b) -&gt; (a,b+a)
  </code></pre>
  
  <p>For instance, <code>(1,1)</code> to <code>(5,4)</code> is <code>True</code>
  You can do the following: Using 2nd move 3 times, <code>(1,1) -&gt; (1,2) -&gt; (1,3) -&gt; (1,4)</code> Using 1st move 1 time <code>(1,4) -&gt; (5,4)</code> <br><br>
  I came up with the following recursive method</p>
  
  <pre><code>def move(a,b,c,d):
      if a==c and b==d:
          return True
      elif a&gt;c or b&gt;d:
          return False
      else:
          ans = False
          if a &lt; c:
              if move(a+b,b,c,d):
                  return True
          if b &lt; d:
              if move(a,b+a,c,d):
                  return True
      return False
  </code></pre>
  
  <p>a) Does my solution cover all the possible cases. I am unable to verify for sure since I do not have test cases, but I think I did take everything into account.</p>
  
  <p>b) What is the time complexity of my solution? I think it is exponential but can't say for sure.</p>
  
  <p>c) Is there a better solution to this (in terms of time complexity). Can we use dynamic programming?</p>
  
  <p>Thank you for any input.</p>