Помнится, богатыри в сказке Пушкина так и ходили всегда стройными рядами, отсортированные по неубыванию роста. А что делать, если подрос новый богатырь? Нужно найти ему место в стройных рядах. Напишите рекурсивную функцию epic_hero(arr, knight), которая вставит элемент в нужное место, чтобы неубывающий порядок сохранился. Использование рекурсии обязательно.

Ниже приведена рекурсивная функция epic_hero, которая вставляет нового богатыря в отсортированный по неубыванию роста массив богатырей.

“`python
def epic_hero(arr, knight):
if len(arr) == 0:
return [knight]
if knight <= arr[0]: return [knight] + arr if knight >= arr[-1]:
return arr + [knight]
if knight == arr[len(arr) // 2]:
return arr[:len(arr) // 2] + [knight] + arr[len(arr) // 2:]
if knight < arr[len(arr) // 2]: return epic_hero(arr[:len(arr) // 2], knight) + arr[len(arr) // 2:] if knight > arr[len(arr) // 2]:
return arr[:len(arr) // 2 + 1] + epic_hero(arr[len(arr) // 2 + 1:], knight)
“`

Шаги решения:

1. Функция epic_hero принимает два аргумента: отсортированный по неубыванию роста массив богатырей `arr` и рост нового богатыря `knight`.
2. Если длина массива `arr` равна 0, это означает, что новый богатырь должен быть первым элементом и возвращается массив, содержащий только нового богатыря.
3. Если рост нового богатыря меньше или равен первому элементу массива `arr`, новый богатырь должен быть вставлен в начало массива, и возвращается массив, содержащий нового богатыря, за которым следуют все остальные элементы массива `arr`.
4. Если рост нового богатыря больше или равен последнему элементу массива `arr`, новый богатырь должен быть вставлен в конец массива, и возвращается массив, содержащий все элементы массива `arr`, за которыми следует новый богатырь.
5. Если рост нового богатыря равен элементу массива `arr`, находящемуся в середине, новый богатырь должен быть вставлен между двумя элементами массива `arr`, находящимися в середине, и возвращается массив, содержащий первую половину массива `arr`, за которой следует новый богатырь, а затем вторая половина массива `arr`.
6. Если рост нового богатыря меньше элемента массива `arr`, находящегося в середине, функция epic_hero вызывается рекурсивно для первой половины массива `arr` и роста нового богатыря `knight`, а затем возвращается результат вызова функции, к которому добавляется вторая половина массива `arr`.
7. Если рост нового богатыря больше элемента массива `arr`, находящегося в середине, функция epic_hero вызывается рекурсивно для второй половины массива `arr` и роста нового богатыря `knight`, а затем возвращается результат вызова функции, к которому добавляется первая половина массива `arr`.