재귀

재귀 조건

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

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

 

재귀에 대한 정보

1) 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 넘겨줄지 정확히 알아야 함

2) 모든 재귀 함수는 반복문만으로 동일한 동작의 함수 구현 가능

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

 

자기 자신을 여러 번 호출하면 비효율적일 수 있음

 

절차지향적 사고를 버려라!

1) 1에서 잘 동작함

2) k에서 잘 동작함

3) k+1에서 잘 동작함 -> (k+1, k, k-1, k-2...)에서도 잘 동작함

 

필요한 것: 함수의 정의 / Base condition / 재귀식

 

BOJ11729 하노이의 탑

#include <bits/stdc++.h>
using namespace std;
void hanoi(int a, int b, int n) {
    if (n == 1) {
        cout << a << ' ' << b << endl;
        return;
    }
    hanoi(a, 6 - a - b, n - 1);
    cout << a << ' ' << b << endl;
    hanoi(6 - a - b, b, n - 1);
}
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    cout << (1 << n) - 1 << endl;
    hanoi(1, 3, n);
}

 

(1 << n) right shift
즉, 오른쪽으로 n번 밀어 2ⁿ

 

아무리 봐도 이해가 안 된다... 일단 후순위로 미뤄놓자 ㅠㅠ