재귀

재귀

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

void func1(int n){ //N부터 1까지 출력하는 함수
    if(n==0) return;
    cout << n << ' ';
    func1(n-1);
}
int func2(int n){ //1부터 N까지의 합을 구하는 함수
    if(n==0) return 0;
    return n+func2(n-1);
}

수학적 귀납법

재귀로 어떠한 문제를 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것인데 이 귀납적인 방식은 지금까지의 문제풀이와 큰 차이가 있다. 위 사진의 도미노를 살펴보자. 모든 도미노가 쓰러지는지 설명해보라고 한다면 두 가지 방법이 존재한다. 편의상 앞에서부터 1번, 2번, ... k번 도미노라고 한다면 첫 번째 설명 방법은 1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가 쓰러지고, ... 이런 식으로 계속 진행되기 때문에 모든 도미노가 쓰러진다는 설명 방법이다.

 

반면 두 번째 설명 방법은 수학적 귀납법을 이용한 방법인데 '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'가 참이니까 모든 도미노가 쓰러진다는 설명 방법이다. 사실 이 두 번째 설명 방법이 맞는 이유도 결국 1번 도미노가 쓰러지고, 이후에 2번 도미노가 쓰러지고 ... 이렇게 연쇄적으로 진행이 되어 모든 도미노가 쓰러지기 때문에 그렇다. 하지만 앞으로는 '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 까지만 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 한다. 즉, 절차지향적인 사고를 탈피해야 한다는 것을 의미한다.

 

N부터 1까지 출력하는 문제로 절차지향적 사고와 귀납적 사고에 대해서 알아보자. 우선 절차지향적 사고로 func1(3)의 출력 결과가 왜 3 2 1 인지 생각해 본다면 이 코드가 동작하는 흐름을 그대로 따라가면 된다.

 

func1(3)가 호출되면 3을 출력하고 func1(2)를 호출한다. func1(2)는 2를 출력한 후에 func1(1)을 호출할거고 func1(1)은 1을 출력한 후에 func1(0)을 호출합니다. 그리고 func1(0)은 02번 줄에 걸려서 종료된다. 이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다.

이번에는 func1 함수가 N부터 1까지 차례로 출력하는 함수임을 귀납적인 사고로 이해해보자. 첫 번째로 func1(1)이 1을 출력한다. 이것은 자명하다. 그 다음이 중요한데, func1(k)가 k k-1 k-2 ... 1을 출력하면, 즉 k부터 1까지 차례대로 출력하면 func1(k+1)은 k+1부터 1까지 차례로 출력한다는 것을 보여야 한다.

 

이걸 보이는 건 func1(k+1)이 호출될 때 어떤 상황이 생기는가를 보면 되는데 k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는 k부터 1까지 차례로 출력한다 가정을 했으니 func1(k+1)은 k+1부터 1까지 차례로 출력함을 알 수 있다.

 

이 두 문장이 참이므로 귀납적으로 func1함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 된다. 

재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition)

모든 입력은 base condition으로 수렴해야 함

재귀에 대한 정보 1

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄

재귀에서는 함수를 명확히 정의해야 한다. 정의라는 것은 함수의 인자로 어떤 것을 받을지, 그리고 어디까지 계산한 후 자기 자신에게 넘겨줄지를 의미한다. 그리고 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다. 재귀는 잘 사용하면 코드가 간결해지지만 함수 호출 비용이 꽤 큰 연산이기 때문에 메모리와 시간에서 손해를 본다. 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없다면 반복문으로 짜는 게 좋지만 재귀 없이 구현을 하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현을 하는 것이 좋다.

재귀에 대한 정보 2

재귀 함수가 자기 자신을 여러번 호출하게 되면 예상과는 달리 굉장히 비효율적일 수 있다. 위의 함수는 n번째 피보나치 수열을 반환하는 함수이다. 

 

Base condition은 n이 1 이하일 때이고, 모든 입력에 대해 Base condition으로 수렴할 것이다. n번째 피보나치 항을 구하기 위해 필요한 연산의 횟수를 생각해보면 상식적으로 생각했을 때 앞에서부터 차례로 1 1 2 3 5 8 ... 이렇게 가면 n번의 덧셈이 필요하다.

 

그런데 이 재귀 함수의 시간복잡도는 놀랍게도 O(1.618ⁿ)이다. 즉 n이 100만 정도만 되어도 일반 컴퓨터로 20000년 넘게 걸린다.

왜 이런 일이 발생했냐고 하면 함수의 호출이 어떤식으로 이루어지는지를 보면 되는데 fibo(5)를 살펴보자. fibo(5)는 fibo(4)와 fibo(3)을 호출하고 fibo(4)는 fibo(3)과 fibo(2)를, fibo(3)은 fibo(2)와 fibo(1)을 호출한다. 전체적인 재귀 호출 상황을 나타내보면 슬라이드의 그림과 같다.

 

이 그림을 보면서 아주 중요한 것 하나를 눈치채면 좋은데, 바로 이미 계산한걸 또 계산한다는 일이 아주 빈번함을 알 수 있다. 당장 fibo(3)만 보더라도 왼쪽에서 fibo(3)을 계산하기 위해 fibo(2)와 fibo(1)을 부르고 fibo(2)는 fibo(1)과 fibo(0)을 부르는 일이 발생했는데 오른쪽에서 또 fibo(3)을 계산하려고 함수를 따라들어가는 짓을 한다. 이렇게 이미 계산한 값을 다시 계산하는 일이 빈번하게 발생해서 시간복잡도가 말도 안되게 커지는 현상이 발생한다. 이와 같이 한 함수가 자기 자신을 여러 번 호출할 경우에는 시간복잡도가 이상하게 될 수 있어서 조심해야 한다.

 

이 문제는 재귀 대신 나중에 다이나믹 프로그래밍을 이용해 O(n)에 해결 가능하다.

int arr[100];
//1 1 2 3 5 8 13 21...
int fibonacci(int n){
    if(n<=2) return 1;
    if(arr[n]!=0) return arr[n]; //이미 계산을 해서 값을 가지고 있다
    else{
        //0이라는 것은 아직 계산이 된 적이 없다는 것
        //계산을 하고 저장해둔다
        //그 후 값을 반환한다
        arr[n] = fibonacci(n-1) + fibonacci(n-2);
        return arr[n];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fibonacci(30); //832040


    return 0;
}

재귀에 대한 정보 3

재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 누적된다. 이 스택 영역이라고 하는 것은 메모리 구조에서의 스택 영역을 말한다. 

 

문제를 풀 때 메모리 제한이 있는데, 스택 메모리가 작게 제한된 곳에서 문제를 푸는데 재귀를 깊게 들어가는 풀이라면 어쩔 수 없이 재귀 대신 반복문으로 문제를 풀어야 한다. 참고로 스택 메모리에는 지역 변수도 들어간다.

재귀 장단점 정리

장점

• 논리가 명확하게 드러나 가독성을 높혀줌

단점

• 함수 호출반환의 overhead 가 있다
• 스택 overflow의 가능성이 있다

출처 : 바킹독님 블로그 https://blog.encrypted.gg/943