C언어의 기초 문법

유클리드 호제법(다시!?)

 유클리드 호제법은 반복문으로 했을 때는 아주 복잡하고 어려웠습니다. 지금 재귀함수에서는 어떻게 되었는지 한 번 보실까요?(lcm은 그냥 a * b / gcd여서 그냥 생략했습니다)

int gcd(int a, int b){
    
    if(b == 0) return a;
    return gcd(b, a % b);
}

순간 '왓... 이렇게 간단해질수가!!'라는 생각이 드셨을 텐데(저도 이 코드를 보고 엄청난 충격을 받았습니다. 예전에 반복문으로 유클리드 호제법을 정리하려고 무려 3시간을 넘게 썼거든요. 결국은 선생님이 알려주시고 겨우 이해했습니다) 네.. 저도 그 마음 이해합니다. 해석은 안 해도 이미 아시겠죠? a % b가 0이 될 때까지 재귀함수가 계속 돌아간다는 것을...

댓글

댓글 본문
  1. Joel
    저도 솔직히 충격받았어요. 어떻게 50줄이 넘던 코드가 5줄이 되지? 라는 질문을 많이 했었어요. 이것이 바로 재귀함수의 힘인 것 같네요;;;
graphittie 자세히 보기