2.1 Recursion에 대한 이해

앞선 내용에서는 Maximum Range Sum을 구하는 함수를 구현하고 거기에서 중복되는 연산부분을 없애는 방식으로 수행 속도를 향상시켰다. 이것을 하는데 있어서는 아무런 사전 지식이 없어도 생각을 해본다면 Live하게 짤 수 있는 알고리즘이었다.

이번에는 Recursion이 무엇인지에 대해 살펴보도록 하겠다.

Recursion을 한국말로 번역을 하자면 '반복'이라는 뜻을 가지고 있다. 즉 Recursive function은 같은 함수가 반복해서 여러 번 불린다는 뜻을 의미한다.

Recursive function을 이용해서 문제를 해결하기 위해서는 기본적으로 Divide & Conquer 전략을 사용한다. 즉, 큰 문제가 있다면 그것을 작은 부분 문제로 쪼개서 해결한 다음 그 결과를 이용해서 큰 문제를 해결하는 방식을 의미한다.

Recursive function으로 쉽게 짤 수 있는 것이 'n번째 Fibonacci number를 계산하기', 'n! 구하기' 등이 있다. 이것을 Recursive function으로 구현할 수 있는 이유는 'n번째 Fibonacci number'의 경우 이전의 두 항의 합을 계산하면 구할 수 있기 때문에 가능하며, 'n!'의 경우에도 n에다가 이전 값인 (n-1)!를 곱하면 되기 때문에 가능하다. 즉 작은 문제의 결과를 이용해서 값을 구할 수 있기 때문에 Recursive function으로 구현을 할 수 있다.

이 밖에도 많은 정렬 알고리즘이나 기타 등등의 알고리즘이 Recursion으로 구현이 가능하다. 그리고 모든 Recursive function은 for이나 while과 같은 반복문을 이용해서 구현을 할 수 있다.

Recursive하게 코딩을 하게 되면 장점이 어떤 문제에 대해서는 쉽게 알고리즘을 작성할 수 있다는 것이며, 이렇게 작성한 경우에는 반복문을 이용해서 작성한 경우보다 소스코드를 좀 더 빨리 이해할 수 있다는 것이다. 이에 대한 내용을 소스코드와 함께 다음 내용에서 살펴보도록 하겠다..

하지만 단점의 경우에는 기본적으로 함수를 호출할 때는 '스택'을 통해서 하는데, Recursive function의 경우에는 '스택'에 계속 함수와 관련된 데이터가 계속 쌓이기 때문에 잘못된 Recursive function을 짜는 경우(예를 들면 초기 조건을 제대로 설정하지 않아서 계속 함수가 call 되는 경우), stack overflow 에러를 볼 수 있게 된다.

그리고 함수를 call 할 때 매개변수만 넣는 것이 아니라 함수의 prologue부분이 추가가 되기 때문에 같은 알고리즘을 반복문으로 짰을 때보다 더 느릴 수밖에 없다.(즉 함수 호출 비용이 비싸다는 것을 알아야 한다.)

이러한 단점이 있더라도 Recursion을 공부하는 이유는 알고리즘 문제를 간단하게 해결할 수 있는 방법이고, 또한 모든 Recursive code는 반복문으로 변경이 가능하지만 대다수의 경우에는 그 과정이 매우 어려우며, 또 코드의 가독성이 매우 떨어지기 때문에 Recursion으로 짜는 것이 더 나을 수도 있다.

다음 글에서는 Recursion code의 몇 가지 예시를 보면서 반복문으로 구현하면 가독성이 얼마나 떨어지는지 비교해보도록 하겠다.