[CDS] chapter 2 : 순환

1. 순환(Recursion) 기본

순환(=재귀)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환은 본질적으로 순환적인 문제에 적합한데, 이 순환적인 문장이 무슨 의미인지 예시를 통해 살펴보자.

 

펙토리얼을 프로그래밍으로 구현하려면 어떻게 해야 할까? 자연수 n을 입력받아서 n부터 1까지 모든 자연수를 곱한 값을 반환해주면 된다는 점에서, 다음과 같이 반복문을 활용해 구현할 수 있을 것이다.

int factorial(int n)
{
    int ans = 1;
    for (int i = n; i > 0; i--){
        ans = ans * i;
    }
    return ans;
}

 

그런데 n! = n * (n - 1)!이라는 점을 생각해보면 펙토리얼은 본질적으로 순환적인 문제로 볼 수 있다. n!을 구하기 위해 자기자신에 해당하는 (n - 1)!을 호출하고 있기 때문이다. 따라서 다음과 같이 순환을 활용한 구현이 가능하다. 아래 예시에서, 순환 알고리즘은 1) 자기 자신을 순환적으로 호출하는 부분과 2) 순환 호출을 종료시키는 부분으로 구성되어 있음을 확인해보자.

int factorial(int n)
{
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

2. 순환과 반복

펙토리얼을 반복문과 순환 두 가지 방법으로 구현해보았는데, 이처럼 반복문과 재귀문은 기본적으로 문제 해결 능력이 동등하고 많은 경우 상호간에 변환할 수 있다. 특히 순환 호출이 끝에서 이루어지는 꼬리 순환(tail recursion)의 경우 반복문으로 쉽게 변환할 수 있다.

 

순환은 반복문에 비해 알고리즘을 훨씬 명확하고 간결하게 나타낼 수 있고 특히 순환적으로 정의되어 있는 문제에 적합다는 장점이 있지만, 함수 호출이 이루어지기 때문에 반복문에 비해 수행속도 면에서는 떨어진다는 단점이 있다. 구체적으로 살펴보면, 순환 호출의 경우 1) 호출이 일어날 때마다 호출하는 함수의 상태를 기억할 여분의 기억공간이 필요하고 2) 함수의 매개변수들을 스택에 저장하는 등의 사전 작업이 필요하다. 따라서 반복과 동일한 시간복잡도를 갖더라도 순환 알고리즘의 사용은 상대적으로 비효율적인 경우가 많다.

3. 순환호출의 내부적 구현

https://lsh424.tistory.com/48

프로그래밍에서 함수 호출이 있는 경우 시스템 스택의 공간에 함수를 위한 공간인 활성 레코드(activation record)가 만들어진다. 이 활성 레코드에는 1) 함수 실행이 끝나고 돌아갈 복귀 주소, 2) 호출되는 함수를 위한 매개변수와 지역변수, 3) 상태정보 등을 포함하고 있다. (참고로, FORTRAN이나 COBOL과 같은 고전적인 언어에서는 지역변수가 없거나 정적으로 할당되기 때문에 순환이 불가능하다)

 

순환호출 또한 일반적인 다른 함수를 호출하는 것과 마찬가지기 때문에, 각 호출마다 새로운 활성 레코드가 생성된다. 순환 호출의 종료조건 전까지 계속하여 스택에 활성 레코드가 쌓이게 되고, 만약 스택이 가득차면 스택 오버플로우(stack overflow)가 되어 프로그램이 비정상적으로 종료되는 원인이 된다.