Вот вам загадка: можно получить бесконечное количество чисел, начиная с числа 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), и при помощи рекурсии проверяет все решения, выдающие число, меньшее или равное требуемому. Не находит, и возвращает