재귀(자기 호출)

재귀 (자기 호출) - Recursion

자기 호출은 컴퓨터 과학 이론의 근간을 이루는 중요한 개념이다. 이것은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다.

별 생각없이 받아들이면 처음 접하는 듯해 보일 수 있다. 하지만, 사실 대한민국 학생들은 기본적으로 고등학교 시절에 이 재귀와 관련된 훈련을 접해왔다. 고등학교 수학에서 배우는 수학적 귀납법이 이와 관련이 깊다. 수열의 점화식도 이 자기 호출의 기초적인 형태이다. 귀납적 사고라는 것은 성격이 같지만 크기가 다른 문제간의 "관계"를 파악하는 것이다.

재귀니 자기 호출이니 말로만 들어서는 어떤 것인지 감이 오지 않는다. 예제 코드를 통해서 알아 보도록 하자.

factorial(n) {

if (n == 1) {

return 1;

}

return n * factorial(n - 1);

}

위의 예제를 보면 factorial(n)이라는 함수 내에서 factorial(n-1)이라는 문장을 통해서 factorial 함수를 호출한다. factorial(n-1) 함수에서는 factorial(n-2)라는 문장을 통해서 또 다시 factorial 함수를 호출할 것이다. 이 반복적인 호출은 매개 변수의 값이 1이 될 때까지 계속될 것이다. 이렇게 함수 내에서 자기 자신을 호출해서 어떤 일을 처리하는 방식을 재귀 호출이라고 한다.

만약, 이 재귀 호출을 보고 반복문을 떠올린 사람이 있다면, 그 사람은 꽤 감이 좋은 사람이라고 할 수 있다. 사실, 반복문을 통해서 구현할 수 있는 모든 작업은 재귀를 이용해서도 구현할 수 있다. 물론, 반복문에 비해 훨씬 적은 문장으로 반복 작업을 할 수 있으니 재귀가 반복문보다 더 좋다고 생각할 수도 있겠지만, 사실 꼭 그렇지도 않다.

재귀의 경우 지속적인 함수의 호출을 통해서 stack을 계속 생성시키게 된다(stack이란 함수내의 지역 변수등을 저장하는 메모리 저장 공간이다). 따라서, 너무 많은 횟수의 재귀를 하다보면 메모리의 낭비가 극심해질 위험이 있다. 게다가, 재귀의 남용과 오용은 스파게티 코드를 만들게 될 수도 있기에 재귀는 늘 신중하게 사용해야 한다. 하지만, 경우에 따라서는 반복문보다 재귀를 사용하는 것이 더욱 더 효율적일 수도 있다. 그러므로, 개발자들은 반복 작업을 구현할 때에 재귀와 반복문 중 어느 것을 사용하는 것이 더 효율적이고 깔끔한 코드를 생성할 수 있을지에 대해서 고민을 해야 한다.