Sirion Apr 28 2017 at 10:42

Пятничный JS: единственно верный способ вычисления факториала

4 min

52K

Введение

Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$ . Казалось бы, что тут сложного? Однако есть свои нюансы.

Например, сравним два самых распространённых способа вычисления факториала.

Через цикл

function factorial(n){
    var result = 1;
    while(n){
        result *= n--;
    }
    return result;
}

Через рекурсию

function factorial(n, result){
    result = result || 1;
    if(!n){
        return result;
    }else{
        return factorial(n-1, result*n);
    }
}

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

В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:

var React = require("react");

var Factorial = React.createClass({
    render: function(){
        var result = this.props.result || 1,
            n = this.props.n;
        if(!n){
	    return <span>{result}</span>
	}else{
	    return <Factorial n={n - 1} result={result*n}/>
	}
    }
});
module.exports = Factorial;

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

Начнём издалека

Какую из возможностей Javascript недолюбливают и недооценивают сильнее всего? Недолюбливают настолько, что про неё даже придумали специальную поговорку? Конечно же, это eval. Можно сказать, что eval — это тёмная сторона Силы. А как мы помним из фильмов Джорджа Лукаса, нет ничего более крутого и впечатляющего, чем тёмная сторона Силы, поэтому давайте попробуем ей овладеть.

Можно было бы запихнуть в строку какой-нибудь из методов, приведённых в начале поста, а затем передать эту строку в eval, но в этом не было бы новизны. Поставим задачу таким образом, чтобы сделать этот хак невозможным. Пусть у нас есть такой вот каркас:

function factorial(n){
    var f = "это единственное место в коде, которое мы имеем право изменить";
    f = f.replace("$", n);
    for(let i = 0; i < n; i++){
        if(parseInt(f)){
            throw new Error("Cheaters are not allowed");
        }
        f = eval(f);
    }
    return parseInt(f);
}

— и мы хотим, внеся изменения лишь в литерал строки f, сделать так, чтобы функция factorial взаправду вычисляла факториал. Вот задача, достойная истинного ситха.

Что-то это напоминает

Нам нужен код, который возвращает код, который возвращает код… Если забыть про конечную задачу — вычисление факториала, то есть одна хорошо известная штука, которая нам подойдёт. Эта штука называется квайн — программа, которая выводит свой собственный текст.

Про квайны на Хабре написано уже немало, потому я напомню лишь основные принципы квайностроительства. Чтобы сделать простейший квайн, нам нужно:

Задать строку, которая содержит весь остальной текст программы.
Подставить в эту строку её же саму
Позаботиться об экранировании символов и прочих мелочах
Вывести получившуюся строку
???
PROFIT

Вооружившись этим знанием, можно написать следующий квайн на js (отступы и переносы строки добавлены для удобства читателя):

var o = {
    q: '\'', 
    b: '\\',
    s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, s: _q_s_q}; console.log(Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s))'
}; 
console.log(Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s));

В строке o.s содержится весь остальной код, а также специальные подстановочные последовательности, начинающиеся с подчёркивания. Страшное выражение внутри console.log заменяет каждую подстановочную последовательность на соответствующее свойство объекта o, что обеспечивает выполнение пунктов 2 и 3 хитрого плана по созданию квайна.

Лирическое отступление

Здесь меня могут поправить: товарищ, это не простейший квайн, а монстр какой-то. Простейший квайн на js выглядит так:

!function $(){console.log('!'+$+'()')}()

Это правда, но не совсем. Такой квайн считается «читерским», поскольку он из тела функции получает доступ к её же тексту. Это почти то же самое, что прочитать с жёсткого диска файл с исходным кодом программы. Моветон, одним словом.

Скрещиваем ежа с ужом

Как же сделать так, чтобы наш квази-квайн модифицировал сам себя, а в результате превратился в одно-единственное число? Давайте забудем пока про вычисление факториала и постараемся просто написать строку, которая «схлопывается» через определённое количество eval'ов. Для этого нам понадобится:

Некий счётчик
Соответствующая ему подстановочная последовательность
Место, где этот счётчик модифицируется
Проверка того, завершён ли обратный отсчёт

Выглядеть это будет примерно так:

var f = 
"var o = {" +
    "q: '\\\''," +
    "b: '\\\\'," + 
    "n: 10," +
    "s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, n:_n, s: _q_s_q}; o.n--; " + 
    "o.n ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s) : 0;'" +
"};" +
"o.n--;" +
"o.n ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s) : 0;"

 for(let i = 0; i < 10; i++){
    f = eval(f);
    console.log(f);
}

Обратите внимание на отсутствие return внутри строки: в нём нет необходимости, eval возвращает значение последнего выражения. Запустив этот код в консоли, можно c благоговением наблюдать, как с каждой итерацией цикла значение n уменьшается на 1. Если кто-то скажет, что для такого эффекта достаточно:

f.replace(/n: ([0-9]+)/, (_, n) => "n: " + (n - 1))

— то у него нет чувства прекрасного.

После этого подготовительного этапа уже совсем нетрудно написать итоговую версию вычисления факториала. Просто добавляется ещё одна переменная и чуть усложняется строчка с изменением.

function factorial(n){
    var f = "var o = {" + 
        "q: '\\\''," +
        "b: '\\\\'," + 
        "r: 1," + 
        "n: $," +
	"s: 'var o = {q: _q_b_q_q, b:_q_b_b_q, r: _r, n:_n, s: _q_s_q}; o.r *= o.n--; " + 
	"o.n ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, o.s) : o.r;'" +
    "};" +
    "o.r *= o.n--;" +
    "o.n ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, o.s) : o.r;"
    f = f.replace("$", n);
  
    for(var i = 0; i < n; i++){
        if(parseInt(f)){
            throw new Error("Cheaters are not allowed.");
        }
	f = eval(f);
    }
    return parseInt(f);
}

Теперь вы можете смело идти на собеседование.

Заключение

С живым кодом можно поиграться здесь. Как и в прошлой статье из рубрики «Пятничный JS» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. С другой стороны, если вы сделаете это на собеседовании, то вам не дадут возможности сделать это на продакшене, и вы не попадёте в ад. Так что делайте это на собеседовании. Спасибо за внимание.

Tags:

Hubs: