Думаем рекурсивно

Мы уже много раз использовали рекурсию, и, как вы, возможно, заметили, тут есть определённый шаблон. Обычно вы определяете базовые случаи, а затем задаёте функцию, которая что-либо делает с рядом элементов, и функцию, применяемую к оставшимся элементам. Неважно, список ли это, дерево либо другая структура данных. Сумма – это первый элемент списка плюс сумма оставшейся его части. Произведение списка – это первый его элемент, умноженный на произведение оставшейся части. Длина списка – это единица плюс длина «хвоста» списка. И так далее, и тому подобное…

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

Похожим образом обстоит дело, если вы рекурсивно обрабатываете числа. Обычно мы работаем с неким числом, и функция применяется к тому же числу, но модифицированному некоторым образом. Ранее мы написали функцию для вычисления факториала – он равен произведению числа и факториала от того же числа, уменьшенного на единицу. Такой рекурсивный вызов не имеет смысла для нуля, потому что факториал не определён для отрицательных чисел. Часто базовым значением становится нейтральный элемент. Нейтральный элемент для умножения – 1, так как, умножая нечто на 1, вы получаете это самое нечто. Таким же образом при суммировании списка мы полагаем, что сумма пустого списка равна нулю, нуль – нейтральный элемент для сложения. В быстрой сортировке базовый случай – это пустой список; он же является нейтральным элементом, поскольку если присоединить пустой список к некоторому списку, мы снова получим исходный список.

Итак, пытаясь мыслить рекурсивным образом при решении задачи, попробуйте придумать, в какой ситуации рекурсивное решение не подойдёт, и понять, можно ли использовать этот вариант как базовый случай. Подумайте, что является нейтральным элементом, как вы будете разбивать параметры функции (например, списки обычно разбивают на «голову» и «хвост» путём сопоставления с образцом) и для какой части примените рекурсивный вызов.