[C++] BOJ1629 (재귀, 귀납적 사고)

[Settpark]

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

• 모든 재귀는 base condition이 있어야 한다. (무한루프를 돌지 않기 위함인 듯함, 주석 부분이 base condition)
• 귀납적 사고를 해야한다. (위의 코드 *1 POW(a, b/2, m) 부분인 듯함, 아직 자세히 이해 못함)
• a^2n = a^n * a^n이니까 POW(a, b/2, m) 이렇게 작성한 듯 함.
• k승을 계산했다는 것은 POW(k)는 POW(k/2)를 가지고 있으니까
• func(k)가 k, k-1, k-2 ... 1을 출력하면 func(k+1)는 k+1 k k-1 ...1을 출력한다. 를 역으로 발상한 듯 하다.
• 아직 잘 모르겠음.