GrokkingAlgorithms/08 max element recursion.py at main · AlexTkDev/GrokkingAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# Поиск наибольшего элемента, используя рекурсию. [O(n)]

# Создаем функцию "find_max_one", которая принимает один входной параметр:
# список "list_one", содержащий элементы для поиска наибольшего из них.
def find_max_one(list_one):
    # Если список "list_two" содержит 0 элементов, то функция "find_max_one" возвращает "None".
    # "None" означает nil (ничто) в Python. Используем, чтобы определять, что значения нет в списке.
    # Функция "len()" возвращает количество элементов в списке.
    # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
    if len(list_one) == 0:
        return None
    # Создаем базовый случай.
    # Базовый случай в рекурсивной функции - это часть функции, в которой описывается
    # условие прекращения работы функции в целях предотвращения зацикливания.
    # Если одна из вызванных рекурсивно копий функции "find_max_one" принимает в качестве параметра список,
    # содержащий 1 элемент, то мы выходим из этой копии функции "find_max_one" и возвращаем первый элемент этого списка
    # предыдущей копии функции "find_max_one" в стеке вызовов, поскольку если список содержит только один элемент,
    # то этот элемент будет наибольшим.
    # Если изначально вызывается функция "find_max_one", которая принимает в качестве параметра список,
    # содержащий 1 элемент, то функция "find_max_one" сразу возвращает первый элемент этого списка,
    # поскольку если список содержит только один элемент, то этот элемент будет наибольшим.
    if len(list_one) == 1:
        return list_one[0]
    # Создаем рекурсивный случай.
    # Рекурсивный случай в рекурсивной функции - это часть функции, в которой функция вызывает сама себя
    # в целях выполнения какой-либо задачи.
    # Если первый элемент больше второго элемента в списке "list_one", то этот второй элемент удаляется
    # при помощи ключевого слова "del" и рекурсивно вызывается новая копия функции "find_max_one"
    # с этим уменьшенным списком "list_one" в качестве параметра.
    # Когда рекурсивно вызывается копия функции "find_max_one", которая принимает в качестве параметра список,
    # содержащий 1 элемент, то срабатывает базовый случай.
    # Копии функции "find_max_one" в стеке вызовов поочередно завершают свою работу
    # и возвращают свои рассчитанные значения предыдущим рекурсивно вызванным копиям функции "find_max_one" до тех пор,
    # пока не завершит работу самая первая вызванная функция "find_max_one".
    if list_one[0] > list_one[1]:
        del list_one[1]
        return find_max_one(list_one)
    # Иначе если первый элемент меньше второго элемента в списке "list_one", то рекурсивно вызывается
    # новая копия функции "find_max_one" со списком "list_one", за исключением первого элемента, в качестве параметра.
    else:
        return find_max_one(list_one[1:])


# Создаем 2 списка и попытаемся найти в них наибольшие элементы.
# Список "my_list1" содержит несколько чисел, а список "my_list2" является пустым.
# Функция "print()" выводит некую указанную информацию на экран или на какое-либо другое устройство вывода.
my_list1 = [2, 0, 6, 9, 7, 7]
my_list2 = []
print(find_max_one(my_list1))
print(find_max_one(my_list2))

# Давайте создадим еще один вариант функции для поиска наибольшего элемента.
# Здесь мы создаем другой рекурсивный случай.
# Создаем функцию "find_max_two", которая принимает один входной параметр:
# список "list_two", содержащий элементы для поиска наибольшего из них.
def find_max_two(list_two):
    # Если список "list_two" содержит 0 элементов, то функция "find_max_two" возвращает "None".
    # "None" означает nil (ничто) в Python. Используем, чтобы определять, что значения нет в списке.
    # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
    if len(list_two) == 0:
        return None
    # Создаем базовый случай.
    # Если одна из вызванных рекурсивно копий функции "find_max_two" принимает в качестве параметра список,
    # содержащий 1 элемент, то мы выходим из этой копии функции "find_max_two" и возвращаем первый элемент этого списка
    # предыдущей копии функции "find_max_two" в стеке вызовов, поскольку если список содержит только один элемент,
    # то этот элемент будет наибольшим.
    # Если изначально вызывается функция "find_max_two", которая принимает в качестве параметра список,
    # содержащий 1 элемент, то функция "find_max_two" сразу возвращает первый элемент этого списка,
    # поскольку если список содержит только один элемент, то этот элемент будет наибольшим.
    if len(list_two) == 1:
        return list_two[0]
    # Создаем рекурсивный случай.
    # Рекурсивно вызывается новая копия функции "find_max_two" со списком "list_two", за исключением первого элемента,
    # в качестве параметра, причем результат работы этой рекурсивно вызванной копии функции "find_max_two" хранится
    # в переменной "sub_max".
    # Любая копия функции "find_max_two" возвращает результат на основе следующего условия:
    # она возвращает первый элемент списка "list_two", если этот первый элемент больше
    # значения переменной "sub_max", иначе возвращается эта переменная "sub_max".
    # Когда рекурсивно вызывается копия функции "find_max_two", которая принимает в качестве параметра список,
    # содержащий 1 элемент, то срабатывает базовый случай.
    # Копии функции "find_max_two" в стеке вызовов поочередно завершают свою работу
    # и возвращают свои рассчитанные значения предыдущим рекурсивно вызванным копиям функции "find_max_two" до тех пор,
    # пока не завершит работу самая первая вызванная функция "find_max_two".
    else:
        sub_max = find_max_two(list_two[1:])
        return list_two[0] if list_two[0] > sub_max else sub_max


# Попытаемся найти наибольшие элементы в списках "my_list1" и "my_list2", используя функцию "find_max_two".
print(find_max_two(my_list1))
print(find_max_two(my_list2))