Recursion

---

🌟 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법
🌟 실제 재귀함수가 쓰이는 곳에서는 매 호출시마다 입력값(파라미터)이 변함
🌟 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 함

🌟 어떤 리스트의 합을 구하는 경우. 단순히 명령형 사고에 익숙해졌다면 이를 O(n)으로 구하고, 그 답에 만족했을 것. 하지만 이 문제는 재귀적으로 생각할 경우 O(log n)만에 해결할 수 있음. 이처럼 기계적 수준의 최적화가 아니라, 더 높은 수준의 생산성과 효율을 추구한다면 평소에 재귀적으로 사고하는 습관을 들여야 함

🌟 재귀 함수의 동작 원리는 기본적으로 DFS에 기반

🌟 문제 풀이에서는 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되기 때문에 최근에 핫한 코딩 테스트들에서도 사용 빈도가 매우 높음

✅ Star_init

//분할정복법
//이 문제의 핵심 : n을 계속해서 재귀호출할 때 3으로 나눠주기
// : 빈 칸을 검사하는 조건이 3으로 나눴을 때 나머지가 1인 것
#include <iostream>
using namespace std;

void star(int i, int j, int n) { //star는 n을 분할해줌
    //cout << " i = " << i << ", j = " << j << ", n = " << n << '\n';
    if ((i / n) % 3 == 1 && (j / n)% 3 == 1) { //빈칸을 검사하는 조건
        cout << " ";
    }
    else if (n / 3 == 0) { //
        cout << "*";
    }
    else {
        star(i, j, n / 3);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) { //0..<n
            star(i, j, n);
        }
        cout << "\n";
    }
}

💻 입력 : 9

💻 출력 :

✅ Hanoi_tower

#include <iostream>
using namespace std;
void hanoi(int n, int start, int to, int bypass)
{
    if(n == 1)
        printf("%d %d\n", start, to);
    else
    {
        hanoi(n-1,start,bypass,to);
        printf("%d %d\n",start,to);
        hanoi(n-1,bypass,to,start);
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1<<num) -1 << "\n"; //1<<num : 2^num -> 시프트연산 표현
    hanoi(num,1,3,2);
}

💻 입력 : 3

💻 출력 :
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3