问如何递归编写乘法算法

EN

def numDigits(x):
  """
  Returns the number of digits in x
  """
  if x == 0:
    return 1

  digits = 0
  while x >= 1:
    x = int(x / 10)
    digits+=1
  return digits

def multiply(x, y):
  x_digits = numDigits(x)
  y_digits = numDigits(y)

  if x_digits != y_digits:
    return -1                    # not valid

  n = x_digits

  if n == 1:                     # checks if x (and y) are only 1 digit
    return x*y                   # single digit multiplication

  half_n = int(n / 2)

  a = int(x / (10**half_n))
  b = x - (a*(10**half_n))
  c = int(y / (10**half_n))
  d = y - (c*(10**half_n))

  ac = multiply(a, c)
  ad = multiply(a, d)
  bc = multiply(b, c)
  bd = multiply(b, d)

  return (10**n)*ac + (10**half_n)*(ad + bc) + bd



assert multiply(1, 2) == 2
assert multiply(10, 20) == 200
assert multiply(15, 21) == 315
assert multiply(1710, 2450) == 4189500
print("all pass!")