[재귀]

재귀

• 하나의 함수에서 자기자신을 다시 호출해 작업을 수행하는 알고리즘이다.
• 절차지향적 사고보다는 귀납적 사고가 필요하다.
• 공부하면서 느낀것이지만 재귀로 짜여진 코드를 보고 하나하나 분석하기 보다는, n=k 일때 n=k+1 도 정의가능하다는 마음가짐으로 코드를 짜보고 분석하는 것이 현명한 것 같다..!

---

재귀의 특징

• 대부분의 재귀함수는 반복문을 통해 만든 함수로 구현할 수 있다.
• 재귀는 반복문을 이용해 작성한 함수보다 시간적/메모리적 손해를 본다.
• 그럼에도 불구하고, 코드작성시 간편하게 작성할 수 있기떄문에 누구나 읽기 쉽고, 유지보수가 편하다는 점에서 장점이 있다.
• 함수호출시 함수는 스택 영역에 쌓이게되며, 대부분 스택영역은 1MB 이다. 또한 로컬 변수도 같이 쌓이게 되기 떄문에 많은 호출이 일어나지 않도록 주의해야한다.

---

연습문제

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

using ll = long long;

ll POW(ll a, ll b, ll m){
  if(b==1) return a % m;
  ll val = POW(a, b/2, m);
  val = val * val % m;
  if(b%2 == 0) return val;
  return val * a % m;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll a,b,c;
  cin >> a >> b >> c;
  cout << POW(a,b,c);
}

• 2^n * 2^n = 2^2n 이라는 특징을 이용해야한다.
• a의 b승 을 구하는 과정은 반복문으로 구성할 시 O(b) 의 시간복잡도를 갖기 때문에 해결할 수
  없다.
• 따라서 이를 재귀적으로 정의해야한다. 위의 특성을 이용해서 val 변수를 a의 2분의 b승으로 mod m으로 정의하고, 이를 다시 제곱하여 2분의 b승을 두번 곱해 재귀적으로 val을 return 한다.

---

// BOJ 11729
#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);
}

• 하노이 탑 문제이다.
• 하노이탑은 n 개의 원판을 옮길때 n-1개의 원판을 2번 기둥으로 옮기고, n번째 원판을 3번 기둥으로 옮기고, 2번 에 있는 원판을 3번 원판으로 옮기면 된다.
• 따라서 1개를 옮길 수 있을때, 2개 .. n개까지 정의가 가능하다. 즉 n개의 원판이 있을때 n+1 개의 원판도 옮길 수 있다.

---

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

int func(int n, int r, int c){
  if(n == 0) return 0;
  int half = 1<<(n-1);
  if(r < half && c < half) return func(n-1, r, c);
  if(r < half && c >= half) return half*half + func(n-1, r, c-half);
  if(r >= half && c < half) return 2*half*half + func(n-1, r-half, c);
  return 3*half*half + func(n-1, r-half, c-half);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, r, c;
  cin >> n >> r >> c;
  cout << func(n, r, c);
}

• 4분할 을 한 뒤, 바라보자. 만약 1사분면에 r,c가 속한다면, 2사분면에 r,c가 속한다면 ... 을 통해 n-1인경우에 4분할을 이루는 사각형들의 넓이를 잘 더하면 해결할 수 있다.

---

개인적으로 재귀가 제일 어렵다. 절차지향적 사고에서 귀납지향적 사고를 하는 것이 제일 힘들다 ㅠㅠ
베이스 컨디션도 고려하고, 함수를 잘 정의해야 되는 것도 힘들다 ...