5
\$\begingroup\$

I'm trying to use recursion to find the closest numbers in a list. I made a program that runs correctly without any errors but I want to know if there's a better way to write 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.

\$\endgroup\$
0

2 Answers 2

8
\$\begingroup\$

There are some comments I'd like to make about your codes before getting to your main question.

Bug/unexpected behavior

It looks like your algorithm expects a sorted list as an input. However, this is never documented and you can easily come up with a failing test case: I expect [5, 16, 10, 15] to return [16, 15], however I get [10, 15].

This can be fixed by working on a sorted list, or at the very least to clearly document that the method expects a sorted list

Undocumented behavior

Test case n°8 returns [10, 15] for input [5, 10, 15]. However, [5, 10] would be equally true. It should be documented what output will be favored in such cases of ties.

Don't use globals

Globals should be avoided, as they make the logic harder reason about and are prone to introducing bugs later on. They can also pollute the namespace if you import * from your module.

The better way to do what you use globals for in this case is to pass these values as arguments:

def closest(List, deff=-1, num1=0, num2=0):
    # do stuff
    return closest(List[1:], deff, num1, num2)

You also use a global variable in your test suite (allPassed). This one can easily be moved into the scope of main()

Conventions

You should follow PEP8 for style conventions, including naming, unless you have a good reason to do otherwise (mostly conforming to existing conventions of the code base you are working on, which is not your case here).

The main difference here would be to rename variable and method names to snake_case.

About recursion

The algorithm you use is a fundamentally iterative one. You look at two consecutive elements of the list, compare their difference with the recorded minimum, then move one step further.

Using recursion on such an algorithm is a waste and brings no benefit. In fact, the recursive call is the last statement in the method (aka tail call recursion), and would be optimized to an iterative method by basically any optimizing compiler. However, Python being an interpreted language, it will not optimize and waste time and resource managing the call stack.

There are legitimate uses for recursive algorithms, but this is not one of them. If you really want to practice recursion, you should find something else to practice with.

Example code

Taking into account these remarks, this is my solution to the problem:

def closest(lst: list):
    '''Find the two closest elements in a list of comparable items.
    If more than one pair have the same difference, returns the smallest pair
    
    >>>closest([1, 3, 4, 10])
    [3, 4]
    >>>closest([1, 1, 1, 2, 2])
    [1, 1]
    >>>closest([1, 9, 8, 3])
    [8, 9]

    Parameters
    ----------
    lst : list
        a list of comparable values

    Returns
    -------
    list
        The two closest elements in the input list
    '''
    lst = sorted(lst)
    v1 = lst[0]
    v2 = lst[1]
    min_diff = v2 - v1
    for i in range(1, len(lst) - 1):
        if lst[i+1] - lst[i] < min_diff:
            v1 = lst[i]
            v2 = lst[i+1]
            min_diff = v2 - v1
    return [v1, v2]
\$\endgroup\$
4
  • \$\begingroup\$ Your doctring is too permissive. The function can't generally handle "comparable items". For example, strings are comparable, but your function can't handle them. \$\endgroup\$ Aug 1, 2022 at 23:33
  • \$\begingroup\$ Yeah could do a typing.Protocol supports def __sub__ , def __lt__ and then accept a list of that \$\endgroup\$
    – Greedo
    Aug 2, 2022 at 12:09
  • \$\begingroup\$ @KellyBundy I didn't know strings were comparable, you learn every day :) But given the function, how would you phrase that limitation? \$\endgroup\$
    – gazoh
    Aug 2, 2022 at 13:54
  • 1
    \$\begingroup\$ Hmm, I don't know a nice existing term for it, so there's a conflict between being accurate but wordy and being not 100% accurate but nice to read. I might just say "numbers". (I can't think of a non-number type with which your solution works. And you could say "numbers" is too permissive as well, since it for example doesn't work with complex numbers, but I'd say that's ok, as "numbers" is typically understood as real numbers or even a subset like integers, and someone even thinking of complex numbers won't be shocked when it doesn't work.) \$\endgroup\$ Aug 2, 2022 at 15:02
5
\$\begingroup\$

gazoh has made excellent points. I won't repeat those, but I'd like to point out an additional item or two.

Input Validation

closest([]) will crash with an IndexError, and closest([100]) will return (0, 0). You should handle lists with less than 2 elements in some fashion, such as raising ValueError("List too short").

Unused Variables

deff1 is assign but never used. It should be removed.

Slicing

List[1:] creates a copy of the list, skipping the first item. If you start with 100 elements, the first recursion creates a 99 element slice, the next creates a 98 element slice, and so on. These copies are unnecessary, unnecessarily wasting time and memory. For instance, your recursion could simply increase an index value, and call the next level with the unmodified list and the new index position.

Test Cases

The abs(...) in your code suggests that you might be looking for the closest adjacent pair in a non-sorted list, like [1, 6, 4, 10, 7, 20], and (6, 4) would be the closest adjacent pair. gazoh's solution would return non-adjacent values (6, 7). You should include test cases which exercise the non-monotonic lists if that is truly the intent.

Alternative Solution

gazoh's example code is better, but it is not the most efficient code either. for i in range(...) should generally be avoided in Python code; it is preferable to loop over container values, not over the container's indices.

Here is my suggestion for solving the problem, assuming sorting the list is not appropriate, and the list is not necessarily monotonic:

from itertools import pairwise

def closest(lst: list):
   '''
   (Doc-string from gazoh's example)
   '''

   if len(lst) < 2:
       raise ValueError("At least 2 values are required")

   return min(pairwise(lst), key=lambda a: abs(a[1] - a[0]))

Left to student:

  • determine what the following items do, and how they work:
    • min(..., key=...)
    • pairwise(...)
    • lambda ...: ...

Note: pairwise is only part of itertools as of version 3.10. If using Python 3.9 or earlier, install and use more_itertools, or use the recipe found in the itertools documentation.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'm still on Python 3.9, I'm glad to learn that itertools.pairwise is a thing now :) \$\endgroup\$
    – gazoh
    Aug 2, 2022 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.