인프런 커뮤니티 질문&답변
작성한 질문수
재귀 부분이 이해가 되지 않습니다.
작성
·
395
0
```
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)가 홀 수 인 경우 해당 작업이 왜 필요한지 이해가 되지 않습니다.
감사합니다.
답변 1
2
큰돌
지식공유자
자 예를 들어 5번 곱한다고 해보죠. 이를 2번짜리 2개와 1번짜리 1개로 나눌 수 있겠죠?
이 때 1번짜리 1개를 처리하는데 홀수인 경우로 따로 if문으로 빼서 하는 작업이 필요한겁니다.
4번 곱한다고 했을 때 2번 2번 딱 떨어지지만 5번인 경우 그렇게 되지가 않거든요.
감사합니다.
강사 큰돌 올림.