Friday JS: the only true way to calculate factorial

Introduction

Factorial calculation is one of the traditional programming tasks for interviews. If someone has forgotten, the factorial of the natural number N is denoted as N! and equals the product of all natural numbers from one to N inclusive. For example, $$$6! = 1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5 \ cdot 6 = $ 72$. It would seem that there is difficult? However, there are some nuances.

For example, compare the two most common ways to calculate factorial.



Many will say that the first method is better, but it is not. Firstly, cycles are no longer in trend, functional programming is now fashionable. Secondly, the more people use the second method, the faster tail optimization recursion optimization will appear in the main JavaScript engines.
')
In any case, both of these methods are too primitive to judge the knowledge of the candidate. But an experienced developer on React.js can already write something like this:

 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; 

Agree, it looks much more solid. However, it can be seen with the naked eye that this is just a variant of recursive computation. The similarity will become even stronger if you rewrite Factorial as a functional component . And, of course, I would not write this habrapost if I were not ready to offer something fundamentally new.

Let's start from afar

Which of the features of Javascript is disliked and underestimated the most? They dislike so much that they even came up with a special saying about it? Of course, this is eval . We can say that eval is the dark side of the Force. And as we remember from the films of George Lucas, there is nothing cooler and more impressive than the dark side of the Force, so let's try to get hold of it.

It would be possible to stuff into a string one of the methods listed at the beginning of the post, and then pass this string to eval , but this would not be new. We set the task in such a way as to make this hack impossible. Suppose we have such a frame:

 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); } 

- and we want, having made changes only in the literal of the string f , to make the factorial function actually calculate the factorial. This is a task worthy of a true Sith.

Something it reminds

We need a code that returns a code that returns a code ... If we forget about the final task - calculating factorial, then there is one well-known piece that will suit us. This thing is called quine - a program that displays its own text.

About quains on Habré, much has already been written, so I’ll only remind you of the basic principles of quay construction. To make the simplest quine, we need:

1. Set a string that contains all the rest of the program text.
2. Substitute this line itself
3. Take care of shielding characters and other trifles
4. Print the resulting string
5. ???
6. PROFIT

Armed with this knowledge, you can write the following quine on js (indents and line breaks are added for the convenience of the reader):

 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])}, os))' }; console.log(Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, os)); 

The os line contains the rest of the code, as well as special wildcard sequences beginning with an underscore. The horrible expression inside console.log replaces each wildcard sequence with the corresponding property of the object o , which ensures the implementation of points 2 and 3 of the clever plan for creating a quine.

We cross a hedgehog with a snake

How to make our quasi-quine modify itself, and as a result turn into a single number? Let's forget about the factorial calculation for now and try to just write a string that “collapses” after a certain number of evals. For this we need:

• Some counter
• The corresponding wildcard sequence
• The place where this counter is modified
• Check whether the countdown is complete

It will look something like this:

 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}; on--; " + "on ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, os) : 0;'" + "};" + "on--;" + "on ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, os) : 0;" for(let i = 0; i < 10; i++){ f = eval(f); console.log(f); } 

Note that there is no return inside the string: it is not necessary, eval returns the value of the last expression. By running this code in the console, you can watch with awe, as with each iteration of the loop, the value of n decreases by 1. If someone says that for such an effect it is enough:

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

- he has no sense of beauty.

After this preparatory stage, it is already quite easy to write the final version of the factorial calculation. Just add another variable and slightly complicates the line with the change.

 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}; or *= on--; " + "on ? Object.keys(o).reduce(function(a, k){return a.split(_q__q + k).join(o[k])}, os) : or;'" + "};" + "or *= on--;" + "on ? Object.keys(o).reduce(function(a, k){return a.split('_' + k).join(o[k])}, os) : or;" 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); } 

Now you can safely go for an interview.

Conclusion

You can play around with live code here . As in the last article from the “Friday JS” column I remind you: if you do something like that in production, you will go to hell. On the other hand, if you do this at an interview, you will not be given the opportunity to do it in production, and you will not go to hell. So do this at the interview. Thanks for attention.