За короткое время изучения веб-разработки я столкнулся с некоторыми сложными концепциями - областью действия, закрытием, моделью согласования и т. Д. - но одной из самых сложных задач для меня была рекурсия. Я буквально часами бился головой о ту или иную рекурсивную функцию, пытаясь понять, что происходит.

В этом посте я подробно расскажу о примере, приведенном Марин Хавербеке в его книге Eloquent JavaScript.

Пойдем прямо к делу. Что такое рекурсия? Рекурсивная функция - это функция, которая вызывает сама себя. Если вы не знали, что функции могут это сделать, ну, они могут! Вы можете думать о рекурсии так же, как о циклах - оба повторяют некоторый код до тех пор, пока не будет выполнено какое-то условие.

Вот пример из Eloquent JavaScript:

function power(base, exponent) {
  if (exponent == 0) {
    return 1;
  } else {
    return base * power(base, exponent - 1);
  }
}

Вышеупомянутая функция найдет результат числа (основания) в степени некоторого другого числа (экспоненты). Мне пришлось некоторое время смотреть на это, прежде чем я понял, что происходит, но в конце концов это имело смысл. Давай пройдемся через это.

  1. Когда вызывается power(), он сначала проверяет, равен ли переданный ему показатель степени 0. Как некоторые из нас, возможно, помнят из школьной алгебры, все, что в степени 0, равно 1. Итак, если показатель степени равен 0, power() возвращает 1.
  2. Если показатель степени отличен от 0, power() возвращает переданное ему основание, умноженное на другой вызов power().
  3. Второй вызов power() отличается от первого в одном важном отношении, а именно, он уменьшает показатель степени на 1.
  4. Если второй вызов power(), уменьшая показатель степени на 1, уменьшает показатель степени до 0, второй вызов power() вернет 1, и все готово. Оператор return разрешит base * 1. Это вряд ли произойдет, поскольку люди обычно не заинтересованы в нахождении, например, 2 в первой степени.
  5. Если показатель степени остается больше 0, снова вызывается power(). Этот процесс продолжается до тех пор, пока экспонента не достигнет 0 и последний вызов power() не вернет 1.
  6. В зависимости от основания и экспоненты оператор возврата будет выглядеть примерно как base * base * ... * 1.

Представьте, что мы хотели бы знать, что такое 2 в квадрате. На диаграмме ниже мы видим вверху, что вызов power(2,2) возвращает 2 * power(2, 2-1). Второй вызов power(2, 2-1) затем возвращает 2 * power(2, (2-1)-1). Последний вызов power(2, (2-1)-1) возвращает 1. У нас осталось выражение 2 * 2 * 1, которое разрешается в 4.

Хотя это довольно круто, не сразу видно, насколько эта функция значительно лучше той же функции, написанной с использованием цикла for или while. Фактически, Хавербеке указывает, что вышеупомянутая рекурсивная функция выполнялась намного дольше, чем аналогичная функция, которую он написал с циклом while.

Однако бывают случаи, когда рекурсивная функция лучше подходит, чем функция, написанная с помощью циклов. Хавербеке иллюстрирует этот момент следующим упражнением: Напишите функцию, которая определяет, может ли быть достигнуто целевое число, начав с 1 и выполнив серию шагов, прибавляя 5 или умножая на 3 на каждом шаге, пока не будет достигнуто целевое число. или превышено. Если это еще не ясно, просто потерпите меня. Функция должна возвращать строку, представляющую серию операций, которые производят целевое число, если оно может быть достигнуто таким образом. В противном случае функция должна вернуть значение null. Например, если задано целевое число 6, функция должна вернуть строку «(1 + 5)». Если задано целевое число 9, функция должна вернуть «(1 * 3) * 3». Для целевого числа 24 функция должна вернуть строку «((1 * 3) + 5) * 3».

Хавербеке отмечает, что в этой проблеме интересно то, что, как показано на диаграмме ниже, начиная с 1 и затем прибавляя 5 или умножая на 3, количество возможных комбинаций сложения и умножения увеличивается в геометрической прогрессии.

Ой! Как мы собираемся проверить все эти различные возможности, чтобы определить, дает ли одна из них наше целевое число? Вероятно, мы могли бы сделать это с помощью серии циклов FOR, но Хавербеке предполагает, что проблема, подобная этой, в которой мы хотели бы проверить каждую из серии возможностей ветвления, особенно хорошо подходит для рекурсивного решения. Вот решение, которое предлагает Хавербеке:

function findSolution(target) {
    function find(current, history) {
        if (current == target) {
            return history;
        } else if (current > target) {
            return null;
        } else {
            return find(current + 5, `(${history} + 5)`) ||
                   find(current * 3, `(${history} * 3)`);
        }
    }
return find(1, "1");
}
findSolution(24);

Мне потребовалось время, чтобы наконец понять, что происходит в этом коде. И я до сих пор испытываю некоторый трепет перед тем, кто придумал решение.

Давай попробуем сломать это. Чтобы достичь 24, мы вызываем findSolution() с аргументом 24. findSolution() затем вызывает функцию find() с аргументами 1 и «1». При первом прочтении вы, возможно, были сбиты с толку, как и я из-за длинного определения find(). Мне потребовалось мгновение, чтобы увидеть, что find() действительно вызывается в конце findSolution(). На самом деле, мне было полезно думать о findSolution следующим образом:

findSolution(target){
    function find(current, history) {...}
    find(1, "1");
}

Итак, где мы были? Верно, findSolution() звонит find(1,'1'). find(1,'1') затем использует выражение IF… ELSE IF, чтобы проверить, равно ли 1 24 или больше 24. После обнаружения, что ни одно из этих значений не является истинным, find() достигает последнего выражения ELSE, где встречается строка return find(current+5, `${history}+5)`) || find(current*3, `${history}*3`).

Здесь все немного усложняется. Что означает эта строка - return find(current+5, `${history}+5)`) || find(current*3, `${history}*3`)? Что ж, выражение ИЛИ вернет в зависимости от того, какая из его сторон, левая или правая, разрешается в true. Обратите внимание, что выражение OR не обязательно возвращает логическое значение true или false. Скорее, он возвращает вещь, чем бы она ни была, которую может разрешить в true. Это может быть логическое значение, число, строка, массив или объект. Как OR решает, можно ли что-то разрешить в true? По сути, все, что НЕ является null, NaN, 0, пустой строкой ("" или '') или undefined, будет преобразовано в true.

Я сказал, что OR вернет любую из его сторон, левую или правую, разрешаемую в true. В частности, он сначала разрешает то, что находится на левой стороне, и если это разрешается в true, выражение OR возвращает все, что находится на левой стороне, даже не удосужившись посмотреть, что находится на правой стороне. Это удобно. Игнорирование правой части может просто сэкономить вам много времени, если то, что находится справа от выражения ИЛИ, представляет собой сложное вычисление.

Итак, find() сначала вызывает find() в левой части выражения OR. Но, как мы видели в случае с функцией power() выше, есть одно важное различие в том, как find() вызывает себя. Он изменяет аргументы, переданные новому вызову find(). 1 становится 1 + 5, а «1» становится (`${history} + 5`). Пусть вас не смущает обозначение `${}`. Строка `(${history} + 5)` - это просто эквивалент ES6 строки "(" + history + " + 5)" из ES5.

Если раньше все было «немного» сложно, то сейчас все усложняется. Пока что findSolution() позвонил find(), который, в свою очередь, позвонил во второй раз. Мне все труднее было следить за многочисленными вызовами find(), которые требуются, чтобы наконец достичь того, который либо (а) возвращает текущее число, равное нашему целевому числу, либо (б) после исчерпания всех возможных комбинаций сложения 5 или умножение на 3, превышает наше целевое число и возвращает null. В итоге я создал диаграмму, которую вы можете увидеть ниже.

Ух! Я знаю, что говорю это много, но давайте разберемся.

  1. В самом верху диаграммы мы начинаем с find(1,"1"). Поскольку 1 не больше и не равно 24, find() вызывает себя.
  2. Мы начинаем с вызова в левой части оператора OR: find(1+5, "1 +5").
  3. Но 6 тоже не равно и не больше 24, поэтому find() снова вызывает себя, снова начиная с левой стороны: find((1+5)+5, "(1+5)+5").
  4. Этот процесс продолжается некоторое время. На схеме я пронумеровал вызовы на find(). Чтобы найти решение, find () потребуется еще 22 итерации, но в процессе много чего происходит.
  5. Как вы можете видеть на диаграмме, find() движется вниз по левой части оператора OR, пока не достигнет ((((1 + 5) +5) +5) +5) +5 (это номер 6 на диаграмме ). Это первый раз, когда find() встречает число, превышающее наше целевое число. Когда find() встречает число, большее целевого числа, оно возвращает null, которое разрешается в false в нашем операторе ИЛИ. Итак, левая часть нашего оператора OR false.
  6. find() затем, впервые, переключается на правую часть оператора ИЛИ ((((1 + 5) +5) +5) +5) * 3 (это номер 7 на диаграмме). Это выражение сокращается до 63, что также больше 24, поэтому этот вызов find() также возвращает null. null преобразуется в false в нашем операторе ИЛИ. Итак, правая часть нашего утверждения - false.
  7. Это означает, что теперь обе стороны выражения find( ((((1+5)+5)+5)+5)+5 ) || find( ((((1+5)+5)+5)+5)*3 ) разрешились в false, что, в свою очередь, означает, что предыдущий вызов find( (((1+5)+5)+5)+5 ) (это номер 5 на диаграмме) также false. Итак, мы снова переключаемся на правую часть этого оператора ИЛИ (((1 + 5) +5) +5) * 3 (это номер 8 на диаграмме).
  8. Весь этот процесс продолжается до тех пор, пока мы, наконец, не дойдем до 24-го вызова find(). Наконец, этот вызов удовлетворяет условию if(current === target) и возвращает нашу строку: «((1 * 3) +5) * 3».

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