Рекурсия
Функция вполне может вызывать сама себя, если она заботится о том, чтобы не переполнить стек. Такая функция называется рекурсивной. Вот пример альтернативной реализации возведения в степень:
function power(base, exponent) {
if (exponent == 0)
return 1;
else
return base * power(base, exponent - 1);
}
console.log(power(2, 3));
// → 8
Примерно так математики определяют возведение в степень, и, возможно, это описывает концепцию более элегантно, чем цикл. Функция вызывает себя много раз с разными аргументами для достижения многократного умножения.
Однако, у такой реализации есть проблема – в обычной среде JavaScript она раз в 10 медленнее, чем версия с циклом. Проход по циклу выходит дешевле, чем вызов функции.
Дилемма "скорость против элегантности" довольно интересна. Есть некий промежуток между удобством для человека и удобством для машины. Любую программу можно ускорить, сделав её больше и замысловатее. От программиста требуется находить подходящий баланс.
В случае с первым возведением в степень, неэлегантный цикл довольно прост и понятен. Не имеет смысла заменять его рекурсией. Часто, однако, программы работают с такими сложными концепциями, что хочется уменьшить эффективность путём повышения читаемости.
Основное правило, которое уже не раз повторяли, и с которым я полностью согласен – не беспокойтесь насчёт быстродействия, пока вы точно не уверены, что программа тормозит. Если так, найдите те части, которые работают дольше всех, и меняйте там элегантность на эффективность.
Конечно, мы не должны сразу же полностью игнорировать быстродействие. Во многих случаях, как с возведением в степень, особой простоты от элегантных решений мы не получаем. Иногда опытный программист сразу видит, что простой подход никогда не будет достаточно быстрым.
Я заостряю на этом внимание оттого, что слишком много начинающих программистов хватаются за эффективность даже в мелочах. Результат получается больше, сложнее и часто не без ошибок. Такие программы дольше писать, а работают они часто не сильно быстрее.
Но рекурсия не всегда лишь менее эффективная альтернатива циклам. Некоторые задачи проще решить рекурсией. Чаще всего это обход нескольких веток дерева, каждая из которых может ветвиться.
Вот вам загадка: можно получить бесконечное количество чисел, начиная с числа 1, и потом либо добавляя 5, либо умножая на 3. Как нам написать функцию, которая, получив число, пытается найти последовательность таких сложений и умножений, которые приводят к заданному числу? К примеру, число 13 можно получить, сначала умножив 1 на 3, а затем добавив 5 два раза. А число 15 вообще нельзя так получить.
Рекурсивное решение:
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, и эта функция весьма полезна. Некоторые операции легче выразить, используя побочные эффекты.
Итог
Эта глава показала вам, как писать собственные функции. Когда ключевое слово function используется в виде выражения, возвращает указатель на вызов функции. Когда оно используется как инструкция, вы можете объявлять переменную, назначая ей вызов функции.
// Создаём f со ссылкой на функцию
var f = function(a) {
console.log(a + 2);
};
// Объявляем функцию g
function g(a, b) {
return a * b * 3.5;
}
Ключевой момент в понимании функций – локальные области видимости. Параметры и переменные, объявленные внутри функции, локальны для неё, пересоздаются каждый раз при её вызове, и не видны снаружи. Функции, объявленные внутри другой функции, имеют доступ к её области видимости.
Очень полезно разделять разные задачи, выполняемые программой, на функции. Вам не придётся повторяться, функции делают код более читаемым, разделяя его на смысловые части, так же, как главы и секции книги помогают в организации обычного текста.
Упражнения
Минимум
В предыдущей главе была упомянута функция Math.min, возвращающая самый маленький из аргументов. Теперь мы можем написать такую функцию сами. Напишите функцию min, принимающую два аргумента, и возвращающую минимальный из них.
console.log(min(0, 10));
// → 0
console.log(min(0, -10));
// → -10
Рекурсия
Мы видели, что оператор % (остаток от деления) может использоваться для определения того, чётное ли число (% 2). А вот ещё один способ определения:
• Ноль чётный.
• Единица нечётная.
• У любого числа N чётность такая же, как у N - 2.
Напишите рекурсивную функцию isEven согласно этим правилам. Она должна принимать число и возвращать булевское значение.
Потестируйте её на 50 и 75. Попробуйте задать ей -1. Почему она ведёт себя таким образом? Можно ли её как-то исправить?
console.log(isEven(50));
// → true
console.log(isEven(75));
// → false
console.log(isEven(-1));
// → ??
Считаем бобы
Символ номер N строки можно получить, добавив к ней .charAt(N) ("строчка".charAt(5)) – схожим образом с получением длины строки при помощи .length. Возвращаемое значение будет строковым, состоящим из одного символа (к примеру, "к"). У первого символа строки позиция 0, что означает, что у последнего символа позиция будет string.length - 1. Другими словами, у строки из двух символов длина 2, а позиции её символов будут 0 и 1.
Напишите функцию countBs, которая принимает строку в качестве аргумента, и возвращает количество символов "B", содержащихся в строке.
Затем напишите функцию countChar, которая работает примерно как countBs, только принимает второй параметр - символ, который мы будем искать в строке (вместо того, чтобы просто считать количество символов "B"). Для этого переделайте функцию countBs.
4. Структуры данных: объекты и массивы
Два раза меня спрашивали: "Скажите, м-р Бэббидж, а если вы введёте в машину неправильные данные, получится ли правильный ответ?". Непостижима та путаница в головах, которая приводит к таким вопросам.
Чарльз Бэббидж, "Отрывки из жизни философа" (1864)
Числа, булевские значения и строки – кирпичики, из которых строятся структуры данных. Но нельзя сделать дом из одного кирпича. Объекты позволяют нам группировать значения (в том числе и другие объекты) вместе – и строить более сложные структуры.
Написание программ, которым мы до сего момента занимались, сильно затруднял тот факт, что они работали только с простыми данными. Эта глава добавит вам в инструментарий понимание структур данных. К её концу вы будете знать достаточно для того, чтобы начать писать полезные программы.
Глава пройдётся по более-менее реалистичному примеру программирования, вводя понятия по мере необходимости. Код примеров будет строиться из функций и переменных, которые мы определяли ранее.