문제
최대 공약수 구하기
해결 방법1
- m >= n인 두 양의 정수 m과 n에 대해서 m이 n의 배수면 gcd(m,n)=n 이고
- 그렇지 않으면 gcd(m, n) = gcd(n, m%n)이다.
CODE1
function gcd1(m, n) {
if (m < n) {
var temp = m
m = n
n = temp
}
if (m % n == 0) {
return n
} else {
return gcd1(n, m % n)
}
}
console.log(gcd1(2, 4))해결 방법2
- gcd(p, q) = p if q=0
- gcd(p, q) = gcd otherwise
CODE2
//간소화
function gcd2(a, b) {
if (b === 0) {
return a
} else {
debugger
return gcd2(b, a % b)
}
}
console.log(gcd2(2, 8));
console.log(gcd2(8, 2)); // 첫번째 재귀호출시 a%b가 0이 됨으로 바로 "true" 반환