Рекурсивное решение:
function findSolution(target) {
function find(start, history) {
if (start == target)
return history;
else if (start > target)
return null;
else
return find(start + 5, "(" + history + " + 5)") ||
find(start * 3, "(" + history + " * 3)");
}
return find(1, "1");
}
console.log(findSolution(24));
// → (((1 * 3) + 5) * 3)
Этот пример не обязательно находит самое короткое решение – он удовлетворяется любым. Не ожидаю, что вы сразу поймёте, как программа работает. Но давайте разбираться в этом отличном упражнении на рекурсивное мышление.
Внутренняя функция find занимается рекурсией. Она принимает два аргумента – текущее число и строку, которая содержит запись того, как мы пришли к этому номеру. И возвращает либо строчку, показывающую нашу последовательность шагов, либо null.
Для этого функция выполняет одно из трёх действий. Если заданное число равно цели, то текущая история как раз и является способом её достижения, поэтому она и возвращается. Если заданное число больше цели, продолжать умножения и сложения смысла нет, потому что так оно будет только увеличиваться. А если мы ещё не достигли цели, функция пробует оба возможных пути, начинающихся с заданного числа. Она дважды вызывает себя, один раз с каждым из способов. Если первый вызов возвращает не null, он возвращается. В другом случае возвращается второй.
Чтобы лучше понять, как функция достигает нужного эффекта, давайте просмотрим её вызовы, которые происходят в поисках решения для числа 13.
find(1, "1")
find(6, "(1 + 5)")
find(11, "((1 + 5) + 5)")
find(16, "(((1 + 5) + 5) + 5)")
too big
find(33, "(((1 + 5) + 5) * 3)")
too big
find(18, "((1 + 5) * 3)")
too big
find(3, "(1 * 3)")
find(8, "((1 * 3) + 5)")
find(13, "(((1 * 3) + 5) + 5)")
found!
Отступ показывает глубину стека вызовов. В первый раз функция find вызывает сама себя дважды, чтобы проверить решения, начинающиеся с (1 + 5) и (1 * 3). Первый вызов ищет решение, начинающееся с (1 + 5), и при помощи рекурсии проверяет все решения, выдающие число, меньшее или равное требуемому. Не находит, и возвращает null. Тогда-то оператор || и переходит к вызову функции, который исследует вариант (1 * 3). Здесь нас ждёт удача, потому что в третьем рекурсивном вызове мы получаем 13. Этот вызов возвращает строку, и каждый из операторов || по пути передаёт эту строку выше, в результате возвращая решение.
Существует два более-менее естественных способа ввода функций в программу.
Первый – вы пишете схожий код несколько раз. Этого нужно избегать – больше кода означает больше места для ошибок и больше материала для чтения тех, кто пытается понять программу. Так что мы берём повторяющуюся функциональность, подбираем ей хорошее имя и помещаем её в функцию.
Второй способ – вы обнаруживаете потребность в некоей новой функциональности, которая достойна помещения в отдельную функцию. Вы начинаете с названия функции, и затем пишете её тело. Можно даже начинать с написания кода, использующего функцию, до того, как сама функция будет определена.
То, насколько сложно вам подобрать имя для функции, показывает, как хорошо вы представляете себе её функциональность. Возьмём пример. Нам нужно написать программу, выводящую два числа, количество коров и куриц на ферме, за которыми идут слова «коров» и «куриц». К числам нужно спереди добавить нули так, чтобы каждое занимало ровно три позиции.
007 Коров
011 Куриц
Очевидно, что нам понадобится функция с двумя аргументами. Начинаем кодить.
// вывестиИнвентаризациюФермы
function printFarmInventory(cows, chickens) {
var cowString = String(cows);
while (cowString.length < 3)
cowString = "0" + cowString;
console.log(cowString + " Коров");
var chickenString = String(chickens);
while (chickenString.length < 3)
chickenString = "0" + chickenString;
console.log(chickenString + " Куриц");
}
printFarmInventory(7, 11);
Если мы добавим к строке .length, мы получим её длину. Получается, что циклы while добавляют нули спереди к числам, пока не получат строчку в 3 символа.
Готово! Но только мы собрались отправить фермеру код (вместе с изрядным чеком, разумеется), он звонит и говорит нам, что у него в хозяйстве появились свиньи, и не могли бы мы добавить в программу вывод количества свиней?
Можно, конечно. Но когда мы начинаем копировать и вставлять код из этих четырёх строчек, мы понимаем, что надо остановиться и подумать. Должен быть способ лучше. Пытаемся улучшить программу:
// выводСДобавлениемНулейИМеткой
function printZeroPaddedWithLabel(number, label) {
var numberString = String(number);
while (numberString.length < 3)
numberString = "0" + numberString;
console.log(numberString + " " + label);
}
// вывестиИнвентаризациюФермы
function printFarmInventory(cows, chickens, pigs) {
printZeroPaddedWithLabel(cows, "Коров");
printZeroPaddedWithLabel(chickens, "Куриц");
printZeroPaddedWithLabel(pigs, "Свиней");
}
printFarmInventory(7, 11, 3);
Работает! Но название printZeroPaddedWithLabel немного странное. Оно объединяет три вещи – вывод, добавление нулей и метку – в одну функцию. Вместо того, чтобы вставлять в функцию весь повторяющийся фрагмент, давайте выделим одну концепцию:
// добавитьНулей
function zeroPad(number, width) {
var string = String(number);
while (string.length < width)
string = "0" + string;
return string;
}
// вывестиИнвентаризациюФермы
function printFarmInventory(cows, chickens, pigs) {
console.log(zeroPad(cows, 3) + " Коров");
console.log(zeroPad(chickens, 3) + " Куриц");
console.log(zeroPad(pigs, 3) + " Свиней");
}
printFarmInventory(7, 16, 3);
Функция с хорошим, понятным именем zeroPad облегчает понимание кода. И её можно использовать во многих ситуациях, не только в нашем случае. К примеру, для вывода отформатированных таблиц с числами.
Насколько умными и универсальными должны быть функции? Мы можем написать как простейшую функцию, которая дополняет число нулями до трёх позиций, так и навороченную функцию общего назначения для форматирования номеров, поддерживающую дроби, отрицательные числа, выравнивание по точкам, дополнение разными символами, и т. п.
Хорошее правило – добавляйте только ту функциональность, которая вам точно пригодится. Иногда появляется искушение создавать фреймворки общего назначения для каждой небольшой потребности. Сопротивляйтесь ему. Вы никогда не закончите работу, а просто напишете кучу кода, который никто не будет использовать.
Функции и побочные эффекты
Функции можно грубо разделить на те, что вызываются из-за своих побочных эффектов, и те, что вызываются для получения некоторого значения. Конечно, возможно и объединение этих свойств в одной функции.
Первая вспомогательная функция в примере с фермой, printZeroPaddedWithLabel, вызывается из-за побочного эффекта: она выводит строку. Вторая, zeroPad, из-за возвращаемого значения. И это не совпадение, что вторая функция пригождается чаще первой. Функции, возвращающие значения, легче комбинировать друг с другом, чем функции, создающие побочные эффекты.
Чистая функция – особый вид функции, возвращающей значения, которая не только не имеет побочных эффектов, но и не зависит от побочных эффектов остального кода – к примеру, не работает с глобальными переменными, которые могут быть случайно изменены где-то ещё. Чистая функция, будучи вызванной с одними и теми же аргументами, возвращает один и тот же результат (и больше ничего не делает) – что довольно приятно. С ней просто работать. Вызов такой функции можно мысленно заменять результатом её работы, без изменения смысла кода. Когда вы хотите проверить такую функцию, вы можете просто вызвать её, и быть уверенным, что если она работает в данном контексте, она будет работать в любом. Не такие чистые функции могут возвращать разные результаты в зависимости от многих факторов, и иметь побочные эффекты, которые сложно проверять и учитывать.
Однако, не надо стесняться писать не совсем чистые функции, или начинать священную чистку кода от таких функций. Побочные эффекты часто полезны. Нет способа написать чистую версию функции console.log, и эта функция весьма полезна. Некоторые операции легче выразить, используя побочные эффекты.
