Egyption Fraction

/// by leakingtapan
///
fn main() {
    let ef = egyption_fraction(147, 256);
    let exp: Vec<String> = ef.iter().map(|e| format!("1/{}", e)).collect();
    println!("{:?}", exp.join(" + "));
}

fn egyption_fraction(n: u64, d: u64) -> Vec<u64> {
    if n == 0 || d == 0 {
        return vec![];
    }

    if n == 1 {
        return vec![d];
    }

    let mut ef = vec![];

    let x = (d as f64 / n as f64).ceil() as u64;
    ef.push(x);

    let new_n = x * n - d;
    let new_d = x * d;
    let gcd = gcd(new_n, new_d);
    ef.append(&mut egyption_fraction(new_n / gcd, new_d / gcd));

    return ef ;
}

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        return a;
    } else {
        return gcd(b, a % b);
    }
}