Шаг 21.
Алгоритмы.
Принцип "разделяй и властвуй". Пример

    На этом шаге рассмотрим еще один пример на применение рекурсии.

    Имеется массив чисел: 2 4 6. Нужно просуммировать все числа и вернуть сумму. Для решения задачи воспользуемся рекурсией.

    Шаr 1: определить базовый случай. Как выглядит самый простой массив, который вы можете получить? Подумайте, как должен выглядеть простейший случай, и продолжайте читать. Если у вас будет массив с О или 1 элементом, он суммируется достаточно просто.

    Итак, с базовым случаем мы определились.

    Шаr 2: каждый рекурсивный вызов должен приближать вас к пустому массиву. Как уменьшить размер задачи? Один из возможных способов:

    В любом случае результат равен 12. Но во второй версии функции sum передается меньший массив. А это означает, что вы сократил и размер своей задачи!

    Функция sum может работать по следующей схеме:

    А вот как это выглядит в действии.

    Вспомните, что при рекурсии сохраняется состояние.

    На языке Python код программы, реализующий подсчет суммы элементов массива используя рекурсию, следующий:

def sum(arr):
    if not arr:
        return 0
    else:
        return arr[0]+sum(arr[1:])

print(sum([2, 4, 6]))

    Архив с примером на языке Python можно взять здесь.

    На следующем шаге начнем рассматривать быструю сортировку.




Предыдущий шаг Содержание Следующий шаг