Три закона рекурсии¶

Подобно роботам Азимова, все рекурсивные алгоритмы должны подчиняться трём важным законам:

1. Рекурсивный алгоритм должен иметь базовый случай.
2. Рекурсивный алгоритм должен изменять своё состояние и двигаться по направлению к базовому случаю.
3. Рекурсивный алгоритм должен вызывать сам себя.

Давайте рассмотрим каждый из этих законов более подробно и найдём примеры их применения в алгоритме listsum. Первый - базовый случай - это условие, которое позволяет алгоритму остановить рекурсию. Он представляет собой задачу настолько малую, что её можно решить без применения каких-либо дополнительных средств. Для алгоритма listsum базовый случай - это список длиной 1.

Чтобы соблюсти второй закон, мы должны организовать изменения состояния таким образом, чтобы алгоритм двигался по направлению к базовому случаю. Изменение состояния означает модификацию каких-то данных, используемых алгоритмом. Обычно объём данных, представленных в задаче, уменьшается каким-либо образом. В алгоритме listsum наша первоначальная структура данных - это список, так что следует сфокусировать усилия по изменению состояние именно на нём. Поскольку базовый случай - список единичной длины, естественным прогрессом в его сторону станет сокращение списка. Это в точности то, что происходит в строке 5 ActiveCode 2, когда мы вызываем listsum с более коротким списком.

Последний закон заключается в том, что алгоритм должен вызывать сам себя. Собственно, в этом и состоит определение рекурсии. Рекурсия - смущающая концепция для многих новичков-программистов. Как начинающий программист вы учили, что функции хороши тем, что позволяют взять большую задачу и разбить её на более мелкие части. Их можно решить, написав функцию для каждой. Когда же мы говорим о рекурсии, то может показаться, что мы собираемся зациклиться. У нас есть задача, решаемая с помощью функции, но для этого ей необходимо вызывать саму себя! Однако, логически здесь ничего не замкнуто: логика рекурсии в элегантном выражении решения задачи с помощью разбиения её на более мелкие и лёгкие подзадачи.

В конце этой части мы рассмотрим много примеров рекурсии. В каждом случае мы сфокусируемся на разработке решения задачи с помощью использования трёх законов рекурсии.