1

Я изучаю рекурсию и решил написать свою, для нахождения наибольшего числа в массиве.

def high(list, max):

    if list == []:

        return max

    elif list[0] > max:

        max = list[0]

    return high(list[1:], max)

list = [1,2,3,4,510,6]

high(list, 0)

Здесь я взял простой пример, но при многих других он тоже работает. У меня по этому коду есть два вопроса:

  1. Является ли это рекурсией вообще?

  2. Корректно ли написана данная рекурсия?

6
  • 3
    Да, рекурсия, да, корректно
    – andreymal
    31 окт 2019 в 12:57
  • Если в массиве будут только отрицательные числа, то выходе вы получите 0, что не является верным ответом. 31 окт 2019 в 12:59
  • @ЮрийКозлов можно вместо 0 написать float('-inf') и всё будет корректно
    – andreymal
    31 окт 2019 в 13:00
  • 1
    Если подходить строго - то претензия есть. Нужно угадать со значением max при начальном вызове, что не есть хорошо. Нужно сделать параметр max опциональным, и? если он не определён, безусловно присваивать ему list[0]. Это даст возможность получить чуть более универсальную функцию - т.е. не просто вернуть максимальное, но и максимальное не менее заданного.
    – Akina
    31 окт 2019 в 13:02
  • 1
    В идеале - на вход функции вообще не должно подаваться значение максимума. На входе должен быть только проверяемый массив, а максимум возвращается как итог ее работы. 31 окт 2019 в 13:05

2 ответа 2

0

Я бы сделал по-другому:

  • На вход подается только список, а не список и число.

  • Сначала обрабатываем тривиальные случаи (база рекурсии) - когда список пустой и когда в нем один элемент. Когда список пустой пусть возвращается None. Когда в списке один элемент - очевидно он и является максимальным.

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

def my_max(s):
    if not s:
        return None
    elif len(s) == 1:
        return s[0]
    else:
        # return max(s[0], my_max(s[1:])
        x = my_max(s[1:])
        if s[0] > x:
            return s[0]
        else:
            return x

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

def my_max(s, i=0):
    if i >= len(s):
        return None
    elif i == len(s)-1:
        return s[i]
    else:
        x = my_max(s, i+1)
        if s[i] > x:
            return s[i]
        else:
            return x
0
  1. Да, это рекурсия.

  2. Написано плохо. Если на вход подать пустой список, то результатом станет параметр max, что очевидно не является верным. Если же в списке не окажется ни одного числа больше, чем max, то результатом опять окажется max, что тоже неверно. Во-вторых, не стоит использовать слово list в качестве имени переменной, потому что это имя встроенной функции.

2
  • «что очевидно не является верным» — неочевидно, такое поведение вполне может быть специально задумано автором этой функции
    – andreymal
    31 окт 2019 в 17:45
  • @andreymal может. Но в условиях про это не сказано, значит, не задумано. 31 окт 2019 в 17:57

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.