Simple recursive transformation solution in Python This simple Python code I wrote for a problem asked during an interview. The problem statement is:


  Given a tuple (a, b), transform this into (c, d) by applying any of the two below operations multiple time in any order you like:
  
  
  (a, b) -> (a+b, b)
  (a, b) -> (a, a+b)
  
  
  The program should take in a, b, c, and d. And tells us if it is possible to transform (a, b) to (c, d).
  
  Edit: a, b, c and d can be negative integers.


This recursive solution seems correct but recursion depth increases very fast for even slight increase in input size. I feel I am missing some easy optimization here. I would be glad for any kind of inputs be it style, algorithm choice, speed etc.

def intro():
  print "This program will check if transformation (a, b) -&gt; (c, d) is possible by recursive application of any of the below rules:"
  print "1. (a, b) =&gt; (a+b, b) \n2. (a, b) =&gt; (a, a+b)\n"

def user_input():
  print "Enter space separated four integers a, b, c and d:\n"
  a, b, c, d = map(int, raw_input().split(' '))
  return a, b, c, d
  # print 'a = ' + a + ' b = ' + b + ' c = ' + c + ' d = ' + d

def solve(a, b, c, d):
  print '(a: {}, b: {})  (c: {}, d:{})'.format(a,b,c,d)
  if a == c and b == d:
    return True
  elif a &gt; c or b &gt; d:
    return False
  elif a == c and b != d:
    return solve(a, a+b, c, d)
  elif a !=c and b == d:
    return solve(a+b, b, c, d)
  else:
    return solve(a+b, b, c, d) or solve(a, a+b, c, d)

if __name__ == '__main__':
  intro()
  a, b, c, d = user_input()
  if solve(a, b, c, d):
    print "Transformation possible"
  else:
    print "Transformation not possible"
Your code works correctly – as far as I can see – for strictly positive
integers \$ a, b, c, d \$. It fails if the integers are allowed to
be zero or negative. For example:


solve(-1, -1, -2, -3) returns False although \$(-1, -1) \$ can
be transformed to \$ (-2, -3) \$.
solve(0, 0, 1, 1) fails with a “maximum recursion depth exceeded”
because it calls itself with the same arguments.


The remainder of this review is based on the assumption that 
\$ a, b, c, d &gt; 0\$.

The number of recursive calls increases quickly with larger input values
because in most cases you have two possible branches at

return solve(a+b, b, c, d) or solve(a, a+b, c, d)


As an example, solve() is called


\$29\$ times to compute that \$(4, 6)\$ is not
reachable from \$(1, 1)\$, and
\$8189\$ times to compute that \$(127, 99)\$ is reachable
from \$(1, 1)\$.


The problem is that one does not know if \$(a, b)\$ should become \$(a+b, b)\$
or \$(a, a+b)\$ in order to reach \$(c, d)\$.

The “trick” to do the transformations backwards. If \$(c, d)\$ is
reached eventually, then the previous pair must be either
\$(c-d, d)\$ or \$(c, d-c)\$. But only one of these is possible, depending on the
sign of \$ c-d \$.

That leads to the following implementation:

def solve(a, b, c, d):
  if a == c and b == d:
    return True
  elif a &gt; c or b &gt; d:
    return False
  elif c &gt;= d:
    return solve(a, b, c - d, d)
  else:
    return solve(a, b, c, d - c)


which is considerable faster: Now solve() is called


\$4\$ times to compute that \$(4, 6)\$ is not
reachable from \$(1, 1)\$, and
\$14\$ times to compute that \$(127, 99)\$ is reachable from \$(1, 1)\$.


The method can still fail with a “maximum recursion depth exceeded” runtime
error. But with this changed algorithm it is easy to replace the 
recursion by an iteration:

def solve(a, b, c, d):
  while c &gt;= a and d &gt;= b:
    if c == a and d == b:
        return True
    (c, d) = (c - d, d) if c &gt;= d else (c, d - c)
  return False


The algorithm itself can be improved further by replacing multiple transformations
$$
(c, d) \to (c-d, d) \to (c-2d, d) \to \ldots
$$
by a single transformation
$$
   (c, d) \to (c - kd, d)
$$
with a suitable integer \$k\$. How large can \$k\$ be chosen?
If that reminds you of the Euclidean algorithm for computing the greatest common divisor then you are on the right
track to implement an optimal method.