Python Minmax, используя только рекурсию

Question

Я пытаюсь создать функцию, которая принимает список и возвращает кортеж (min, max).

Например,

[2,1,4,9,4.5]

вернется

(1, 9)

Я пытаюсь использовать только рекурсию и хочу выполнить эту задачу, не используя другие вещи, которые сделали бы это очень простым (например, min (), max (), sort (), sorted (), loop..etc)

До сих пор я был в состоянии создать функцию, которая находит максимум

def findmax(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]])
    elif alist[0] <= alist[1]:
        return findmax([alist[1]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmax([alist[0]] + alist[2:])
    elif alist[0] <= alist[1]:
        return findmax(alist[1:])

, которая

findmax([2,1,4,9,4.5])

возвращает

(9,)

и функция, которая находит минимум (который не слишком отличается)

def findmin(alist):
  if len(alist) <= 1:
    return tuple(alist)
  elif len(alist) == 2:
    if alist[0] >= alist[1]:
        return findmin([alist[1]])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]])
  elif len(alist) > 2:
    if alist[0] >= alist[1]:
        return findmin(alist[1:])
    elif alist[0] <= alist[1]:
        return findmin([alist[0]] + alist[2:])

, которая

findmin([2,1,4,9,4.5])

возврат

(1,)

Есть ли способ объединить эти две отдельные функции в одну, используя только рекурсию, чтобы она возвращала желаемый результат

(1, 9)

Любая помощь будет принята с благодарностью.

Answer 1

Ниже minmax выражается с использованием стиля продолжения. В этом стиле все наши переменные состояния извлекаются из эфира. Дополнительные примеры других программ, написанных с использованием этого стиля, см. в этом ответе .

from math import inf

def first (xs):
  return xs[0]

def rest (xs):
  return xs[1:]

def tuple2 (a, b):
  return (a, b)

def minmax (xs = [], then = tuple2):
  if not xs:                 # base case: no `x`
    return then (inf, -inf)
  else:                      # inductive case: at least one `x`
    return minmax \
      ( rest(xs)
      , lambda a, b:
          then \
           ( min (a, first (xs))
           , max (b, first (xs))
           )
      )

print (minmax ([ 2, 1, 4, 9, 4.5 ]))
# (1, 9)

print (minmax ([]))
# (inf, -inf)

min и max определены как

def min (a, b)
  if a < b:
    return a
  else:
    return b

def max (a, b)
  if a > b:
    return a
  else:
    return b

Answer 2

Найти максимум или минимум по отдельности легко. Что сложно, так это найти максимальное и минимальное значения с помощью рекурсивных вызовов. Хвостовая рекурсия как раз для этого (поддерживает и обновляет состояние переменных с помощью рекурсивных вызовов) и обычно проста для записи:

def findminmax(L):
    def inner(L1, min, max):
        if L1 == []:
            return (min, max)
        elif L1[0] > max:
            return inner(L1[1:], min, L1[0])
        elif L1[0] < min:
            return inner(L1[1:], L1[0], max)
        else:
            return inner(L1[1:], min, max)
    return inner(L[1:], L[0], L[0])

findminmax([2,1,4,9,4.5])
# => (1, 9)

Нет необходимости в присвоении и индексации необычного списка. Требуется только самая основная операция со списком. Структура рекурсии ясна и очень стандартна (очевидно, см. Базовый случай, сокращение и рекурсивный вызов функции), и код также очень читабелен как обычный английский.

Обновление

Небольшая модификация для обработки строкового ввода и пустого списка или строкового ввода:

def findminmax(LS):
    def inner(LS1, min, max):
        if not LS1:
            return (min, max)
        elif LS1[0] > max:
            return inner(LS1[1:], min, LS1[0])
        elif LS1[0] < min:
            return inner(LS1[1:], LS1[0], max)
        else:
            return inner(LS1[1:], min, max)
    try:
        return inner(LS[1:], LS[0], LS[0])
    except IndexError:
        print("Oops! That was no valid input. Try again...")

findminmax([2,1,4,9,4.5])
# => (1, 9)

findminmax([2])
# => (2, 2)

findminmax('txwwadga')
# => ('a', 'x')

findminmax('t')
# => ('t', 't')

findminmax([]) # empty list
# => Oops! That was no valid input. Try again...

findminmax('') # empty string
# => Oops! That was no valid input. Try again...

Answer 3

Вы определенно чрезмерно усложняете рекурсивную функцию. Минимальное и максимальное значения могут быть возвращены в кортеже с помощью следующего рекурсивного кода.

my_list = [2,1,4,9,4.5]

def recursive_min_max(list_a, pos, biggest, smallest):
    if pos != len(list_a) - 1:
        biggest_new = list_a[pos] if biggest == None else list_a[pos] if list_a[pos] > biggest else biggest
        smallest_new = list_a[pos] if smallest == None else list_a[pos] if list_a[pos] < smallest else smallest
        return recursive_min_max(list_a, pos + 1, biggest_new, smallest_new)
    return (biggest,smallest)


print(recursive_min_max(my_list, 0, None, None))

На каждом шаге текущий элемент списка сравнивается с текущими самыми большими и самыми маленькими элементами. Если они больше / меньше, их заменяет текущее значение.

Answer 4

Я считаю, что такого рода проблемы, как правило, проще, чем вы ожидаете. Пусть рекурсия сделает всю работу:

def find_min_max(a_list):

    if a_list:
        head, *tail = a_list

        if tail:
            minimum, maximum = find_min_max(tail)

            return [head, minimum][minimum < head], [head, maximum][maximum > head]

        return head, head

    return a_list

* ИСПОЛЬЗОВАНИЕ 1005 *

>>> find_min_max([2, 1, 4, 9, 4.5])
(1, 9)
>>> find_min_max('elephant')
('a', 't')
>>> 

Это решение относится только к Python 3, но может быть легко изменено для совместимости с Python 2 и 3.

Answer 5

Вы можете добавить еще def (читать комментарии):

def f(l):
    return findmin(l)+findmax(l) # Also you can do: `(findmin(l)[0],findmax(l)[0])`

Теперь, чтобы позвонить, сделайте:

print(f([2,1,4,9,4.5]))

Вывод будет:

(1, 9)