Write in the beginning: personal “talent and learning”, small white one, the following content is the summary of notes in the learning process and personal feeling, if there is any mistake please correct

About the title: the title is the road to Cultivation. One is that I used to be a fan of fairy cultivation novels, and the other is that I was inspired by a book written by The great God Yang Yifei

Preliminary knowledge

Greatest common divisor

The greatest common factor, also known as the greatest common divisor, the greatest common factor, refers to two or more integers common divisor of the largest one.

Euclidean algorithm

Theorem: The greatest common divisor of two integers is equal to the greatest common divisor of the smaller number and the remainder of their division. The Greatest Common Divisor is abbreviated as GCD.

If we need to find the greatest common divisor of two positive integers 1997 and 615, the Euclidean algorithm works like this:

1997/615 = 3 (remaining 152)

615/152 = 4(remainder 7)

152/7 = 21(remainder 5)

7/5 = 1 (remainder 2)

5/2 = 2.

2/1 = 2 (remainder 0)

At this point, the greatest common divisor is 1

When the remainder is 0, the divisor of the current formula is taken as the greatest common divisor, so the greatest common divisor of 1997 and 615 is 1.

See baidu Encyclopedia here for the above explanation

Code implementation

Basic Logic edition

function gcd(i,j) {
// Determine the size of the input argument, declare the remainder to be res and calculate the remainder
var res = Math.max(i,j) % Math.min(i,j);
// Check whether the remainder is 0, if 0, output the minimum parameter
if (res === 0) return Math.min(i,j);
// The function is recursively evaluated until the remainder is 0
return res = gcd(Math.min(i,j),res); 
}
// Console output maximum common divisor
console.log(gcd(24.36));
Copy the code

Basic logic edition optimization

function gcd(i,j) {
// Declare and count the remainder
var res = Math.max(i,j) % Math.min(i,j);
// The trinary operator determines whether the remainder is zero. If it is zero, the minimum is output. If it is not zero, the remainder and minimum are then recursed as parameters
return res === 0 ? Math.min(i,j) :res = gcd(Math.min(i,j),res);
}
console.log(gcd(115.22));
Copy the code

Super Logic

function gcd(m,n) {
// ？？？？？？？？？？？
return n ? gcd (n,m % n) : m
}
console.log(gcd(24.36));
Copy the code

At the beginning, Wu and Fan said that I didn’t believe him when he solved the problem with one line of code. I thought for a long time, how could it be two lines of code? And then… Normally speaking, I think people may fall into the same mistake as me. That is, how to say that the parameters passed in should be compared to the size of the mod bar, so it is necessary to judge, so that I can not understand the code. Here’s how the above line of code works:

Recursive logic process:

The GCD (4); //gcd(m,n) -> return n ? gcd(n,m % n) : m -> 36 ? GCD (36, 24%) : 24; 1 - > 24? GCD (24, 36%24) : 36; 2 - > 12? GCD (12, 240%) : 24 3 -> 0? (Condition false, end recursion): 12; 4Copy the code

Q1: Why does this code not need to compare the size of two parameters? I don’t know if you remember the phrase % operation (I don’t remember it, and I can’t think of it either (whisper beep)). If the dividend is smaller than the divisor, the remainder is itself

According to the recursive logic process above, from Formula 1, we deliberately give the decimal to m and the large number to N. After the first call, n is judged to be true to perform the recursion, and the remainder m % n plays a very important role here, which is to reassign the decimal to n in the next recursion. Therefore, he eliminates the effect of parameter size order on function by using % arithmetic rule!!

Q2: Why is the trinary operator judged to be n? In fact, if you understand the process in the beginning of the preliminary knowledge, we will know that the argument n appears to judge, but in fact, the argument n is the identity of the remainder of the recursive call! So the judgment here should be read as: Determine whether the remainder is 0!

Q3: Why does the last false statement return m in the execution statement of the trinary operator? This problem is similar to Q2. We only need to understand that m is covered by constant assignment in the recursive process. Its essential identity is the smallest number divided (or modulo) every time, that is, when the remainder is 0 after the last mod, the smallest value is the largest common divisor of the two numbers passed in at the beginning!

conclusion

All the time, my logical thinking has always stayed on the surface, just like when learning English, I can only transliterate, not free translation, but when I deeply understand the connotation, I can truly realize the beauty of it!