Get two closest numbers in a list using recursion in python-CodePudding

I'm trying to use recursion to find the colosest numbers in a list. I made a program that runs corectly without any errors but I want to know if there's a better way to right my program while still using recursion.

This is my program:

deff = -1
num1 = 0
num2 = 0
def closest(List):
    global deff, num1, num2
    deff1 = -1
    if deff == -1:
        deff = max(List) - min(List)
        deff1 = max(List) - min(List)
    if len(List) == 1:
        deff = -1
        return [num1, num2]
    if abs(List[0] - List[1]) <= deff:
        deff = abs(List[0] - List[1])
        num1 = List[0]
        num2 = List[1]
    return closest(List[1:])

This is my Tester Program:


from recursion import *
allPassed = True

def closestMain():
    global allPassed    
    testCases = [(1, [3, 7, 67, 68, 210, 215], [67, 68]),
                 (2, [3, 7, 67, 168, 210, 215], [3, 7]),
                 (3, [3, 47, 67, 168, 210, 215], [210, 215]),
                 (4, [3, 7], [3, 7]),
                 (5, [3, 3, 3, 3, 3, 3], [3, 3]),
                 (6, [1, 2, 3, 4, 5, 6], [5, 6]),
                 (7, [5, 10, 100, 105, 305, 310], [305, 310]),
                 (8, [5, 10, 15], [10, 15])]
    
    for num, L, expected in testCases:
        result = closest(L)
        if result != expected:
            print(f'Closest Test {num} Failed. Expected {expected} got {result}')
            allPassed = False

def main():
    closestMain()
    if allPassed:
        print('All tests passed')

    
main()

Again no errors, the program works fine, just trying to see if there's a better way to do it using recursion.

CodePudding user response：

decomposed recursion

closest could be a recursive program, but it's a setup for a complex and tightly-coupled program. The high-level way to express the solution is using min and combinations, two generic functions, each of which could be implemented using recursion -

from itertools import combinations

def closest(l):
  return min(combinations(l, 2), key=lambda pair: abs(pair[0] - pair[1]))

tests = [
  (1, [3, 7, 67, 68, 210, 215], (67, 68)),
  (2, [3, 7, 67, 168, 210, 215], (3, 7)),
  (3, [3, 47, 67, 168, 210, 215], (210, 215)),
  (4, [3, 7], (3, 7)),
  (5, [3, 3, 3, 3, 3, 3], (3, 3)),
  (6, [1, 2, 3, 4, 5, 6], (5, 6)),
  (7, [5, 10, 100, 105, 305, 310], (305, 310)),
  (8, [5, 10, 15], (10, 15))
]

for num, lst, expected in tests:
  print(f"#{num} {expected} {closest(lst)}")

no.	expected	actual
1	(67, 68)	(67, 68)
2	(3, 7)	(3, 7)
3	(210, 215)	(210, 215)
4	(3, 7)	(3, 7)
5	(3, 3)	(3, 3)
6	(5, 6)	(1, 2)
7	(305, 310)	(5, 10)
8	(10, 15)	(5, 10)

Notice the earliest closest numbers are returned, unlike the latest that are expected in your output. Using the built-in min function we cannot control which minimum is returned, however we can supply our own recursive implementations and get the output we expect -

def combinations(t, n):
  if n <= 0:
    yield ()
  elif not t:
    return
  else:
    for x in combinations(t[1:], n - 1):
      yield (t[0], *x)
    yield from combinations(t[1:], n)

def min(t, key = lambda x: x):
  def loop(a):
    try:
      b = next(t)
      return loop(b if key(b) < key(a) else a)
    except StopIteration:
      return a
  return loop(next(t, None))

If we rerun the tests, we see the output is the same. So how can we control it?

getting the exact output

Because we wrote min we now have the power to change how it behaves. Instead of returning the earliest minimum value in the series, we can return the latest. This is easily accomplished by reordering the if..else -

def min(t, key = lambda x: x):
  def loop(a):
    try:
      b = next(t)
      return loop(a if key(a) < key(b) else b) # <--
    except StopIteration:
      return a
  return loop(next(t, None))

Rerun the tests to see the updated output -

for num, lst, expected in tests:
  print(f"#{num} {expected} {closest(lst)}")

no.	expected	actual
#1	(67, 68)	(67, 68)
#2	(3, 7)	(3, 7)
#3	(210, 215)	(210, 215)
#4	(3, 7)	(3, 7)
#5	(3, 3)	(3, 3)
#6	(5, 6)	(5, 6)
#7	(305, 310)	(305, 310)
#8	(10, 15)	(10, 15)

using iterables correctly

Writing min using recursion is a fun exercise, but there's a more ergonomic way to interact with python's iterables. The simple for..in loop is fast and doesn't risk overflowing the stack -

def min(t, key = lambda x: x):
  a = next(t, None)
  for b in t:
    a = a if key(a) < key(b) else b
  return a

Rerun the tests and verify the output is identical.

CodePudding user response：

here is my attempt, this algorithm works for sorted lists:

def closest(list_, close=None):
    if len(list_) < 2: return close
    if not close: return closest(list_[1:],list_[:2])
    a,b = list_[:2]
    x,y = close
    return closest(list_[1:], (a,b) if b-a <= y-x else (x,y))