[단계별로 풀어보기] 재귀

1. 팩토리얼

#include <iostream>

using namespace std;

int n;
int a=1;

void run(int le) {

    a *= le;

    if (n <= 1) {
        cout << 1;
        return;
    }

    if (le == n) {
        cout << a;
        return;
    }
   
    run(le + 1);
    
}

int main() {

    cin >> n;

    run(1);

    return 0;
}

 

2. 피보나치 수 5

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> p;

void run(int le) {

    if (le == n) {
        cout << p[n];
        return;
    }

    p.push_back(p[le] + p[le - 1]);

    if (n <= 1) {
        cout << n;
        return;
    }

    

    run(le + 1);

}

int main() {

    cin >> n;

    p.push_back(0);
    p.push_back(1);

    run(1);

    return 0;
}

3. 별 찍기 - 10

#include<iostream>

using namespace std;

// n=3인경우 -> (1,1) (1,4) (1,7) (1,10),...
// n=9인경우 -> (3,3) (3,4) (3,5) / (4,3) (4,4) (4,5) / (5,3) (5,4) (5,5)
 
void run(int i, int j, int n) {
    if ((i / n) % 3 == 1 && (j / n) % 3 == 1) {
        cout << " ";
    }
    else {
        if (n / 3 == 0) 
            cout << "*";
        else {
            run(i, j, n/3);
        }
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            run(i, j, n);
        }
        cout << '\n';
    }

    return 0;
}

4. 하노이 탑 이동 순서

//하노이탑 이동경로 -> N번째 판을 c로 이동시키기위해 N-1까지 b로 먼저 이동, b에서 c로 이동
//시간초과시 endl -> \n 변경 (그래도 시간초가나오면 scanf, printf)

#include <iostream>
#include <vector>
#include <cmath> //pow사용시 필요함

using namespace std;
// ㅡ ㅡ ㅡ
//  A  B  C

//A판에있는 n-1개의 원판을 B판으로
//A판에 남은 가장 큰원판을 C판으로
//B판의 n-1개의 원판을 C판으로

void hanoi(int n, int start, int by, int to) { //원판수, 출발지, 경유지, 목적지
   //재귀를 돌면서 출발지, 경유지, 목적지가 섞임

    if (n == 1)
        cout << start << " " << to << '\n';

    else    {
        hanoi(n-1, start, to, by); //a판의 n-1개의 원판을 b판으로 옮기는 과정
        //a판에서 c판을 이용해 b판으로 옮긴다.
        cout << start << " " << to << '\n'; //a판의 가장큰 원판 c판으로 옮기기 출력
        hanoi(n - 1, by, start, to); //b판의 n-1의 원판을 c판으로 옮기는 과정
        //b판에서 a판을 이용해 c판으로 옮긴다.
    }

}

int main() {
    int n;
    cin >> n;

    int count=1;
    // 이동횟수는 2의 n제곱 -1
    for (int i = 1; i <= n; i++) {
        count *= 2;
    }

    cout << count - 1 << '\n';

    hanoi(n, 1,2,3); //a판 b판 c판

    return 0;
}