0x0B. 재귀 - 함수의 재귀적 호출

0x0B 재귀

0x00 알고리즘 설명

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

수학적 귀납법

도미노를 예로 들면, "1번 도미노가 쓰러진다.", "k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다"가 참이니까 모든 도미노가 쓰러진다는 것이다. 즉 지금까지 당연하게 생각하던 절차지향적인 사고를 탈피해야 한다.

절차지향적 사고

귀납적 사고

재귀 함수의 조건 : 반드시 특정 입력(base condition or base case)에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. 모든 입력은 base condition으로 수렴해야 한다.

재귀의 대한 정보

함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함

모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음

재귀는 반복문으로 구현했을 때에 배해 코드가 간결하지만 메모리/시간에서는 손해를 봄

한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음

EX_ 피보나치 :

이미 계산한걸 또 계산하는 것이 빈번하다. 시간복잡도 O(1.618^n)로 n에 대한 지수함수 만큼의 시간이 걸림

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨

→ 일부 컴파일 환경에서는 스택 영역의 메모리가 별도로 1MB로 제한되어 있기도 한다. 채점 사이트에서도 swexpertacademy.com에는 제한이 걸려있다. 따라서 스택 메모리가 작게 제한된 곳에서 문제를 푸는데 풀이가 재귀를 깊게 들어가는 풀이라면 어쩔 수 없이 재귀 대신 반복문으로 문제를 풀어야한다. 스택 메모리에는 지역 변수도 들어간다.

0x01 연습문제1 - 거듭제곱

BOJ 1629번 : 곱셈

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

using ll = long long;
ll pow(ll a, ll b ,ll c) {
    if(b == 1) return a % c; // base condition
    ll val = pow(a, b/2, c);
    val = val * val % c;
    if(b % 2 == 0) return val;
    return val * a % c;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int a, b, c;
    cin >> a >> b >> c;
    cout << pow(a, b, c) << "\n";
}

시간복잡도 : O(log b)

→ base condition을 잘 잡아뒀고 k승의 결과를 토대로 2k, 2k+1승의 결과를 계산할 수 있으니 마치 도미노를 쓰러트리는 것처럼 모든 결과가 잘 계산될 것이다로 함수를 이해하는 귀납적인 사고!

0x02 연습문제2 - 하노이 탑

BOJ 11729번 : 하노이 탑 이동 순서

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

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

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

함수의 정의 void func(int a, int b, int n) : 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수
base condition m = 1일 때 cout << a << " " << b << "\n";
재귀 식 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);

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

void hanoi(int a, int b, int n) {
    if(n == 1) {
        cout << a << " " << b << "\n";
        return;
    }
    hanoi(a, 6-a-b, n-1);
    cout << a << " " << b << "\n";
    hanoi(6-a-b,  b, n-1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    cout << (1<<n)-1 << "\n";
    hanoi(1, 3, n);
}

→ <<는 left shift, 따라서 2^n-1로 옮긴 횟수를 의미

0x03 연습문제3 - Z

BOJ 1074번 : Z

함수의 정의 void func(int n, int r, int c)
base condition n = 0일 때 return 0;
재귀 식 (r,c)가 1번 사각형일 때 → return func(n-1, r, c); (r,c)가 2번 사각형일 때 → return half x half + func(n-1, r, c-half); (r,c)가 3번 사각형일 때 → return 2 x half x half + func(n-1, r-half, c); (r,c)가 4번 사각형일 때 → return 3 x half x half + func(n-1, r-half, c-half);

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

int func(int n, int r, int c) {
    if(n == 0) return 0; // base condition

    int half = 1<<(n-1);
    if(r < half && c < half) return func(n-1, r, c); // 1번 사각형
    else if(r < half && c >= half) return half*half + func(n-1, r, c-half); // 2번 사각형
    else if(r >= half && c < half) return 2*half*half + func(n-1, r-half, c); // 3번 사각형
    else return 3*half*half + func(n-1, r-half, c-half); // 4번 사각형
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, r, c;
    cin >> n >> r >> c;
    cout << func(n, r ,c) << "\n";
}

문제 풀이

이번 강의에 해당하는 문제는 총 10개였다.

연습문제는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 나머지 체크표시있는 기본문제, 응용문제를 풀어보면서 재귀와 귀납적 사고를 길러보려고 한다.

Note_ 1780번 종이의 개수, 2630번 색종이 만들기, 1992번 쿼드트리 : 이 기본문제 3문제는 비슷한 유형의 문제였다. 첫번째 문제를 풀때는 오래걸렸지만 2,3번째 문제는 거기서 응용이 되는 문제여서 확실히 감을 잡을 수 있었다.

함수의 정의 void func(int n, int a, int b) // n과 시작점 (a,b)
base condition 3^n × 3^n의 데이터가 모두 같으면 해당하는 배열칸을 증가 후 return
재귀 식

n /= 3
for(int i=0; i<3; i++)
  for(int j=0; j<3; j++)
    func(n/3, a + i*n, b + j*n)

2447번 별찍기 - 11 : 재귀함수로 별찍기란 쉽지 않았다. 그래도 이 문제까지는 어떻게든 아이디어는 떠올렸지만 구현에 있어서 제한이 있었고 코드를 참고해서 풀어낼 수 있었다.

먼저 2차원 배열을 선언하고 공백으로 초기화 ( char board[102][102] )

함수의 정의 void func(int n, int a, int b) // n과 시작점 (a,b)
base condition n==1이 되면 해당하는 칸을 '*'로 변경 후 return
재귀 식

for(int i=0; i<3; i++)
  for(int j=0; j<3; j++) {
    if(i==1 && j==1) continue;
    func(n / 3, x + n / 3 * i, y + n / 3 * j);
  }

2448번 별찍기 - 12 : 다음 별찍기 응용문제는 더 어려웠다 ,, 많이 고민을 해봤지만 전혀 방법이 떠오르지 않았다. 그래서 코드를 참고하며 다시 공부하고 구현해보았다.

먼저 똑같이 2차원 배열을 선언한다.

함수의 정의 void func(int n, int a, int b) // n과 삼각형의 위쪽 꼭짓점 위치 (a,b)
base condition n==3이 되면 해당칸을 기준으로 높이가 3인 삼각형을 만들고 return
재귀 식 위쪽 삼각형 → func(n/2, a, b) 왼쪽아래 삼각형 → func(n/2, a + n/2, b - n/2) 오른쪽아래 삼각형 → func(n/2, a + n/2, b + n/2)

리뷰

재귀함수는 많이 접해보긴 했지만 절차지향적 사고로 문제를 풀어왔고, 익숙하지 않았다.

당연히 재귀함수 코드를 보면 절차지향적으로 생각하여 코드이해에 많은 시간을 뺏겼고 재귀, 말만 들어도 아직 두려운 상태였다.

이렇게 재귀함수에 대해 잘 강의해주셔서 머리에 쏙쏙 들어오고 귀납적 사고로 생각하려고 많이 노력하였다.

기본문제와 응용문제를 풀어보면서 더 많은 생각을 할 수 있었고 머리가 아픈 시간들이였다 ,,ㅎ

재귀에 대해 다시 한번 다듬고, 다음은 0X0C 백트래킹으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의