На этом шаге рассмотрим еще один пример на применение рекурсии.
Имеется массив чисел: 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 можно взять здесь.
На следующем шаге начнем рассматривать быструю сортировку.
