[바킹독 실전 알고리즘 0x0B] 재귀

알고리즘 설명

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

 

다음과 같이 간단한 재귀 함수 코드를 생각해볼 수 있다. 

void func(int n){
    if(n == 0) return;
    cout << n << ' ';
    func(n-1);
}

어떤 문제를 재귀로 푼다는 것은, 수학적 귀납법을 사용해 문제를 해결한다는 것이다. 수학적 귀납법은 평소 우리의 사고 과정과 큰 차이가 있다. 전자는 귀납적 사고, 후자는 절차 지향적 사고라고 부른다. 이 둘의 차이를 도미노를 예로 들어 설명할 수 있다.

 

다음과 같이 세워진 도미노 중 맨 앞의 도미노를 쓰러뜨리면, 그 뒤의 모든 도미노들이 쓰러진다는 사실은 자명하다. 그런데 왜 모든 도미노들이 쓰러질까? 에 대한 설명을 하는 방법은 크게 두 가지가 있다.

 

첫번째로, 1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가, 3번이 쓰러지면 4번이, ... 이런 현상이 계속 진행되기 때문에 결국 모든 도미노가 쓰러지게 된다는 설명 방법이 있다.

 

두번째로는 수학적 귀납법을 사용해 설명하는 방법이 있다. '1번 도미노가 쓰러진다.' 가 참이고 k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다.' 참이면 모든 도미노가 쓰러진다는 설명이다.

 

앞으로는 재귀 문제를 접할 때 첫번째 방법으로 생각하지 말고, '1번 도미노가 쓰러진다.' 와 'k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다.'는 조건을 보게 되면 바로 모든 도미노가 쓰러진다는 결론에 도달해야 한다. 

 

 

재귀 함수의 조건

1. 올바른 재귀 함수는 특정 입력에 대해서는 무조건 자기 자신을 호출하지 않고 종료되어야 한다. 이 조건을 Base Condition이라고 부른다.

2. 재귀함수의 모든 입력은 Base Condition으로 수렴하게 된다. 

 

이 두 조건 중 하나라도 만족하지 못한다면 재귀함수가 무한히 돌아가다가 런타임에러가 발생하게 된다.

 

재귀에 대한 정보 1

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간 면에서는 손해이다. 따라서 굳이 재귀를 사용하지 않아도 구현이 쉬운 함수들은 반복문으로 작성하는 것이 좋다.  다양한 문제를 풀면서 자연스럽게 어떨 때 재귀를 사용하는 것이 유리하고 어떨 때 그렇지 않은지 알게 될 것이다. 

재귀에 대한 정보 2

• 재귀함수가 자기 자신을 여러 번 호출하게 되면 예상과는 달리 굉장히 비효율적일 수 있다. 피보나치 수열을 재귀로 구현하는 상황이 이에 해당한다. 

int fibo(int n){
    if(n <= 1 ) return 1;
    return fibo(n-1) + fibo(n-2);
}

피보나치 수열에서는 직전의 두 개 항을 더해 현재 항을 구한다. fibo(5)를 호출했을 때 필요한 연산을 트리 형태로 그리면 위와 같다. 같은 값을 계속해서 여러 번 계산하는 것을 알 수 있다.  이미 계산한 값을 다시 계산해서 시간복잡도가 말도 안되게 커졌다. 이와 같이 한 함수가 자기 자신을 여러 번 호출할 경우 시간 복잡도가 엄청 커질 수 있음을 주의해야 한다. 이런 문제는 재귀 대신 다이나믹 프로그래밍을 사용해 O(n)에 해결할 수 있다. 

 

재귀에 대한 정보 3

• 재귀함수가 자기 자신을 부를 때 메모리의 스택 영역에 계속 누적이 된다. 코딩테스트에서는 메모리 제한이 있다. 이중 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 제한되어 있는 경우가 있다. 만약 스택 메모리가 작게 제한되어있는 상황인데 본인의 풀이가 재귀를 깊게 들어간다면 어쩔 수 없이 재귀 대신 반복문을 사용해야 한다.

 

연습문제1 - 거듭제곱

a^b mod m, 즉 a^b를 m으로 나눈 나머지는 어떻게 구할 수 있을까?

int func(int a, int b, int m){
    int val = 1;
    while(b--) val *= a;
    return val % m;
}

위와 같은 코드로 6^100 mod 5를 구하려고 하면 int overflow가 발생한다. 따라서 계산하려는 값을 한꺼번에 구하는 게 아니라, 6을 100번 곱하는 중간 중간 계속 5로 나누어 나머지만 챙겨가야 한다. 

using ll = long long;
ll func(ll a, ll b, ll m){
    ll val = 1;
    while(b--) val = val * a % m;
    return val;
}

 

연습문제2 - 하노이탑

BOJ 11729번)

idea)

n-1개의 원판을 기둥 1에서 기둥 2로 옮긴다.

n번 원판을 기둥1에서 기둥3으로 옮긴다.

n-1개의 원판을 기둥2에서 기둥3으로 옮긴다.

->원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때에도 옮길 수 있다.

 

원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.

원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.

따라서 수학적 귀납법에 의해 n개의 원판을 옮길 수 있다.

 

step1)함수의 정의

void func(int a, int b, int n) 원판 n개를 기둥 a에서 기둥 b으로 옮기는 방법을 출력하는 함수

step2)base condition

n=1일 때 cout << a << ' ' << b << '\n';

step3)재귀 식

n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.  func(a, 6-a-b, n-1);

n번 원판을 기둥 a에서 기둥 b로 옮긴다.  cout << a << ' ' << b << '\n';

n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.  func(6-a-b, b, n-1);

 

C++ code)

#include <bits/stdc++.h>
using namespace std;

void func(int a, int b, int n){
    if(n == 1){
    	cout << a << ' ' << b << '\n';
        return;
    }
    func(a, 6-a-b, n-1);
    cout << a << ' ' << b << '\n';
    func(6-a-b, b, n-1);
}
int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    int k;
    cin >> k;
    cout << (1<<k) - 1 << '\n';
    func(1,3,k);
}

(1<<k)는 2^k이다.