Грокаем а Иллюстрированное пособие для программистов и любопытствующих

def sum(arr): total = 0 for x in arr: total += x return total
print sum([l, 2, 3, 4])
Но как сделать то же самое с использованием рекурсивной функции?
Шаг 1: определить базовый случай. Как выглядит самый простой массив, который вы можете получить? Подумайте, как должен выглядеть про­стейший случай, и продолжайте читать. Если у вас будет массив с 0 или 1 элементом, он суммируется достаточно просто.
Итак, с базовым случаем мы определились.
Шаг 2: каждый рекурсивный вызов должен приближать вас к пустому мас­сиву. Как уменьшить размер задачи? Один из возможных способов:
=
БАЗОВЫЙ
СЛУЧАЙ



£ J О ЭЛЕМЕНТОВ = СУММА РАВНА О


1 ЭЛЕМЕНТ = СУММА РАВНА 1


12
2-М0 =12
В любом случае результат равен 12. Но во второй версии функции sum передается меньший массив. А это означает, что вы сократили размер своей задачи!
Ф
ПОЛУЧИТЬ
СПИСОК

ункция sum может работать по следующей схеме:
Ь
ЕСЛИ СПИСОК ПУСТ, ВЕР­НУТЬ О
П РОТИ В НОЛЛ СЛУЧАЕ РЕЗУЛЬ­ТАТ РАВЕН СУММЕ ПЕРВОГО ЧИСЛА В СПИСКЕ И СУММЫ ОСТАЛЬНОГО СПИСКА
А
ОБА ЭТИХ
РЕЗУЛЬТАТА.
РАВНЫ


Son


\


2. +


(шэз)
■J' _ч
Сеш)
J-
4-+ -sovni
X
БАЗОВЫЙ СЛУЧАЙ1
£vjY>\(2\) “ 6 •


4-t- 6



РЕЗУЛЬТАТ
» ‘ ,
:П:
' Г
2 +10 -¹²
Г
= 10


ЬСПОМНИТЕ, ЧТО РЕКУРСИЯ СОХРАНЯЕТ СОСТОЯНИЕ ЭТИХ ЧАСТИЧНО ЗАВЕРШЕННЫХ ВЫЗОВОВ ФУНКЦИИ


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


НИ ОДИН ИЗ этих ВЫЗОВОВ ФУНКЦИИ НЕ ЗАВЕРШИТСЯ ДО ТОГО, КАК БУДЕТ ОБНАРУЖЕН БАЗОВЫЙ СЛУЧАЙ1



о* засипи)


2+ somCSI])


I
4- + som¹


2+10 М2


т


4- + 6 =10



БАЗОВЫЙ СЛУЧАЙ!
Sw«v\(pD) = &■


ПЕРВЫЙ ВЫЗОВ ФУНКЦИИ, КОТОРЫЙ БУДЕТ РЕАЛЬНО ЗАВЕРШЕН

вот как это выглядит в действии.
П
СОВЕТ
Когда вы пишете рекурсивную функцию, в которой задействован массив, ба­зовым случаем часто оказывается пустой массив или массив из одного эле­мента. Если вы не знаете, с чего начать, — начните с этого.

АРА СЛОВ О ФУНКЦИОНАЛЬНОМ ПРОГРАММИРОВАНИИ
Зачем применять рекурсию, если задача легко решается с циклом? Вполне резонный вопрос. Что ж, пора познакомиться с функцио­нальным программированием!
В языках функционального программирования, таких как Haskell, циклов нет, поэтому для написания подобных функций приходит­ся применять рекурсию. Если вы хорошо понимаете рекурсию, вам будет проще изучать функциональные языки. Например, вот как вы­глядит функция sum на языке Haskell:
sum [] = 0 < Базовый случай
sum (x:xs) = х + (sum xs) < Рекурсивный случай
На первый взгляд кажется, что одна функция имеет два определе­ния. Первое определение выполняется для базового случая, а вто­рое — для рекурсивного случая. Функцию также можно записать на Haskell с использованием команды if:
sum агг = if arr == [] then 0
else (head arr) + (sum (tail arr))
Но первое определение проще читается. Так как рекурсия широко применяется в языке Haskell, в него включены всевозможные удоб­ства для ее использования. Если вам нравится рекурсия или вы хо­тите изучить новый язык — присмотритесь к Haskell.
Упражнения

1. 
   Н
   апишите код для функции sum (см. выше).
   
2. 
   Напишите рекурсивную функцию для подсчета
   

элементов в списке.

3. 
   Найдите наибольшее число в списке.
   
4. 
   Помните бинарный поиск из главы 1? Он тоже относится к классу алгоритмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?
   

Быстрая сортировка
Б ыстрая сортировка относится к алгоритмам сортиров­ки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Например, в стандартную библиотеку С входит функция с име­нем qsort, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии «разделяй и властвуй».
В
г


сортировать