非再帰と再帰でユークリッドの互除法を実装する

やること

非再帰と再帰でユークリッドの互除法を実装します。

非再帰の場合

function gcd1(m, n)
    while m % n ≠ 0
        r = m % n
        m, n = n, r
    end

    return n
end

@show gcd1(30, 40)
@show gcd1(29, 13)
@show gcd1(73, 241)

結果になります。

yuu@penguin:~/src/daikon/20240313$ julia gcd1.jl 
gcd1(30, 40) = 10
gcd1(29, 13) = 1
gcd1(73, 241) = 1

再帰の場合

function gcd2(m, n)
    if m % n == 0
        return n
    end

    gcd2(n, m % n)
end

@show gcd2(30, 40)
@show gcd2(29, 13)
@show gcd2(73, 241)

結果になります。

yuu@penguin:~/src/daikon/20240313$ julia gcd2.jl 
gcd2(30, 40) = 10
gcd2(29, 13) = 1
gcd2(73, 241) = 1