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

Введение

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

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

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 взаправду вычисляла факториал. Вот задача, достойная истинного ситха.

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

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

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

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

Вооружившись этим знанием, можно написать следующий квайн на 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 хитрого плана по созданию квайна.

!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, r: _r, 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» напоминаю: если вы сделаете что-нибудь подобное на продакшене, то попадёте в ад. Спасибо за внимание.

ссылка на оригинал статьи https://habrahabr.ru/post/327544/