재귀 부분이 이해가 되지 않습니다.

Question

``` ll go(ll a, ll b){     if(b == 1) return a % c;     ll _c = go(a, b / 2);     _c = (_c * _c) % c;     if(b % 2)_c = (_c * a)% c;     return _c; } ``` 해당 go 함수에서 인자, a, b 를  a 는 숫자 로, b 는 지수로 생각했습니다. 그래서 지수가 1 인 경우 a % c 를 통해 반환하고   `ll _c = go(a, b /2)` 구문과 그 밑은  2^10 == 2^5 * 2^5 이므로 해당 과정을 수행한다고 생각합니다.   근데 (여기서 질문) ``` if(b % 2) {   _c = (_c * a)% c; } ``` - 지수(b)가 홀 수 인 경우 해당 작업이 왜 필요한지 이해가 되지 않습니다.   감사합니다.

큰돌 · Answer

자 예를 들어 5번 곱한다고 해보죠. 이를 2번짜리 2개와 1번짜리 1개로 나눌 수 있겠죠?  이 때 1번짜리 1개를 처리하는데 홀수인 경우로 따로 if문으로 빼서 하는 작업이 필요한겁니다. 4번 곱한다고 했을 때 2번 2번 딱 떨어지지만 5번인 경우 그렇게 되지가 않거든요.   감사합니다. 강사 큰돌 올림.