dsa/algorithms/
intro_algorithm.rs

1/// Performs the Euclidean Algorithm on `a` and `b` to
2/// calculate the greatest common divisor (GCD) between
3/// `a` and `b`
4/// 
5/// # Parameters
6/// - `a`: An unsigned 64-bit integer
7/// - `b`: An unsigned 64-bit integer
8/// 
9/// # Returns
10/// - An unsigned 64-bit integer representing 
11/// the greatest common divisor of `a` and `b`
12/// 
13/// # Examples
14/// ```
15/// use dsa::algorithms::intro_algorithm::euclidean_algorithm;
16/// 
17/// assert_eq!(euclidean_algorithm(20, 5), 5);
18/// ```
19pub fn euclidean_algorithm(mut a: u64, mut b: u64) -> u64 {
20    while b != 0 {
21        let temp = b;
22        b = a % b;
23        a = temp;
24    }
25    
26    a
27}
28
29/// Performs the Euclidean Algorithm **recursively** on `a` and `b`
30/// to calculate the greatest common divisor (GCD) between
31/// `a` and `b`
32/// 
33/// # Parameters
34/// - `a`: An unsigned 64-bit integer
35/// - `b`: An unsigned 64-bit integer
36/// 
37/// # Returns
38/// - An unsigned 64-bit integer representing the
39///   greatest common divisor of `a` and `b`
40/// 
41/// # Examples
42/// ```
43/// use dsa::algorithms::intro_algorithm::euclidean_algorithm_recursion;
44/// 
45/// assert_eq!(euclidean_algorithm_recursion(20, 5), 5);
46/// ```
47pub fn euclidean_algorithm_recursion(a: u64, b: u64) -> u64 {
48    if b == 0 {
49        return a;
50    }
51    
52    euclidean_algorithm_recursion(b, a % b)
53}