[재귀 알고리즘] 홀수 여부 확인

isOdd

 

* Q)  수를 입력받아서 홀수인지 여부를 리턴한다

* 입력받는 num은 int 타입의 정수

* 출력은 boolean 타입을 리턴해야 한다

* 반복문, 나눗셈, 나머지 연산자는 금지

* 0은 짝수로 간주한다

● 입출력 예시

int output = isOdd(17);
system.out.println(output); // --> true

output = isOdd(-8);
system.out.println(output); // --> false

---

▶ 사고 과정

int 타입의 num을 입력을 받고
이 num을 반복문으로 돌릴 수도 없을 뿐더러 
아주 간편한 나머지 연산자를 활용해서 짝홀 구분하는 코드도 쓸 수 없다

문제 해결에 있어서 여러 조건들이 필요한데
일단 문제에서 0은 짝수로 간주한다 했으니 

if (num == 0) {
    return false;
    }

 

조건을 작성을 먼저 해준다

그 다음 생각해볼만한 것은 

입력을 받는 num은 int 타입이지만 음수도 들어올 수 있다는 점이다

일반적으로 짝홀을 구분하는 건 양수일 때라서 절대값 처리를 해줄 필요가 있다고 생각했다

if(num < 0){
      num = -num;
    }

이러면 음수가 들어와도 양수로 바꿔줄 수 있다

이제 문제 풀이에 필요한 전제 조건들을 세워줬으니

본격적으로 재귀 요소를 이용해서 풀어볼 차례다

가장 작은 단계부터 시작을 한다면

역시 1, 3, 5, ... 

이중에 1이겠지

1은 그냥 빼도 박도 못하는 홀수다

위에 if 조건문(0은 짝수) 의 else if로 밑에 달아준다

if(num < 0){
   num = -num;
    }

if (num == 0) {
    return false;
    }

else if (num == 1){
    return true;
    }

사실상 가장 작은 단위 base case는 완성이 된 모습이다 

이러고 남은 나머지 경우를 재귀 호출을 이용해 리턴한다면 문제는 풀릴 것 이다

if(num < 0){
   num = -num;
 }

if (num == 0) {
    return false;
 }

else if (num == 1){
    return true;
 }
 
else
return isOdd(num - 2);

 

애초에 문제에서 나누기 연산자를 쓰지말라고 했는데

사실 어떤 수에서 -2를 (반복적으로) 빼는 것은

나누기 연산이랑 비슷한 결과를 출력한다
어떠한 수가 0이나 1이 될 때까지 -2를 반복해보자

7이라는 수에서 0이나 1이 될 때까지 -2 를 반복하면 
7-2 = 5
5-2 = 3
3-2 = 1

6이라는 수에서 0이나 1이 될 때까지 -2를 반복하면
6-2 = 4
4-2 = 2
2-2 = 0

1이 남아버리게 되는 7은 홀수
0이 남아버리게 되는 6은 짝수

다시 문제로 돌아가서,
코드의 전체적인 흐름은

입력 받는 num 값이 음수일 때 양수로 바꾸기

만약 num이 0이면 false

그렇지않고 num이 1이면 true

이마저도 아니면,
다시 자신을 호출,  isOdd() 메소드에 파라미터로 num - 2를 해주면

어떤 수가 입력되더라도 

0이나 1이 나올 때까지 계~속 -2를 해주게 될 것이다 (재귀)

왜 하필 -2인지 궁금할 수 있는데
위에서 언급했듯이

어떤 수에서 -2를 계속 반복하면 나눗셈, 나머지 연산과 유사한 결과가 나오고
1이나 0으로 떨어질 수 있기 때문에 -2를 사용한 것이다