순환(Recursion)의 소개

순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. (재귀는 초기항과 수열을 이루는 규칙을 통해 수열을 간결하게 표현할 수 있는 점화식의 개념을 컴퓨터에서 구현한 것과 같다.)

순환 호출의 내부적인 구현

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉, 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 파라미터와 지역 변수를 스택으로부터 할당 받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(Activation Record)라고 한다.

이러한 준비가 끝나면 호출된 함수의 코드 시작 위치로 이동하여 수행을 시작한다. 만약 호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다. 혼출된 함수가 끝나게 되면 시스템 스택에서 복귀주소를 꺼내 자신을 호출한 함수로 되돌아간다. 순환 호출이 계속 중첩될 수록 시스템 스택에는 활성 레코드들이 쌓이게 된다.

Untitled

Untitled

C, C++, Java, PASCAL 등의 거의 모든 프로그래밍 언어에서 순환을 지원하지만 FORTRAN, COBOL, BASIC에서는 지역변수가 없거나 있더라도 정적으로 할당되므로 순환이 불가능하다. 즉, 함수 호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수가 없어서 호출이 불가능하다.

순환 알고리즘의 구조

순환 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다. 만일 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 에러를 내면서 멈출 것이다.

순환 <-> 반복

프로그래밍 언어에서 어떤 일을 되풀이하는 방법에는 반복(iteration)과 순환(recursion)의 2가지가 있다. 반복은 문제를 간결하고 효율적으로 해결할 수 있으며 우리에게 익숙한 방식이다. 반면 어떤 문제들은 반복을 사용하면 지나치게 복잡해지는 경우도 있는데, 이런 경우에는 순환이 좋은 해결책이 될 수 있다. 예컨대 트리 알고리즘으로 트리의 순회나 노드의 삽입과 삭제 등에는 순환이 좋다. 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 매우 효율적이다.

기본적으로 순환과 반복은 그 표현 능력이 같으며 많은 경우 특히 순환 호출이 끝에서 이뤄지는 순환 알고리즘의 경우는 반복으로 간단히 바꿀 수 있다. 순환은 어떤 문제에 대해서는 반복에 비해 알고리즘을 명확하고 간결하게 나타낼 수 있다는 장점이 있지만, 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서 떨어진다.

순환의 원리

주어진 문제를 더 작은 동일한 문제들로 분할하여 해결하는 방법을 분할 정복(divide and conquer)라고 한다. 중요한 것은 순환 호출이 일어날 때마다 문제의 크기가 작아진다는 점이다. 문제의 크기가 점점 작아지면 풀기가 쉬워지고 결국은 아주 풀기 쉬운 문제가 된다.

순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리한 방법이다. 팩토리얼 함수 계산, 피보나치 수열, 이항계수 계산, 각종 이진트리 알고리즘, 이진 탐색, 하노이탑 문제들은 순환 알고리즘을 쓰는 것이 자연스러운 알고리즘이다.

순환 알고리즘의 성능

반복 알고리즘과 순환 알고리즘의 시간 복잡도는 동일하다. 그러나 순환 호출의 경우 여분의 기억 공간이 더 필요하고, 또한 함수를 호출하기 위해 함수의 파라미터들을 스택에 저장하는 것과 같은 사전 작업이 상당히 필요하다. 따라서 수행 시간도 더 걸린다.

거듭제곱 값 계산

흔하지는 않지만 순환이 더 빠른 예도 있다. x의 n 제곱을 구하는 함수의 경우 반복을 이용해 구하면 n의 갯수만큼 곱셈이 발생하지만 (O(n)), xn = (x2)n/2의 공식을 이용하여 순환적으로 계산하면 O(log2n)이 되어 더 빠르게 계산할 수 있다. –이 알고리즘의 경우 순환을 돌 때마다 문제의 크기가 하나씩 줄어드는게 아니라 절반씩 줄어든다.