Codestates/Java

자바 재귀 함수를 이용하여 짝수, 홀수 구분하기

진태양 2022. 11. 17. 22:31

오늘 수업 때는 재귀 함수를 배웠다.

재귀 함수라는 것 자체를 처음 들었고, 개념 자체도 좀 난해했다.

현업에서는 잘 쓰이지 않는다고 하지만, 코딩 테스트에서는 나오는 개념이라고 하니 확실히 알아두어야 할 것 같다.

 

오늘 풀었던 연습 문제를 어떻게 해결했는지 과정을 적어보려고 한다.

 

문제

수를 입력받아 짝수인지 여부를 리턴한다.

입력

인자 1 : num

int 타입의 정수

출력

boolean 타입

주의 사항

• 함수 isOdd는 재귀 함수 형태로 작성한다.

• 반복문 사용은 금지된다.

• 나눗셈, 나머지 연산자 사용은 금지된다.

• 0은 짝수로 간주한다.

입출력 예시

int output = isEven(13);
system.out.println(output); // --> false

output = isEven(-6);
system.out.println(output); // --> true

 

처음에 풀었던 방식은 base case로 if(num == 0) return true;를 하고 재귀 호출을 하면서 호출한 값을 부정하는 방식으로 구상했다.

 

public class RecursiveExample {
	public boolean isEven(int num) {
    		num = Math.abs(num);		// num값이 음수인 경우를 위해 절댓값을 쓴다.
        	if(num == 0) return true;	// num이 0일때 true를 리턴한다.
        	return !isEven(num - 1);	// 호출한 재귀 함수의 값을 부정한다. 
    }
}

 

이 코드도 기능적으로는 동작을 하는데, 재귀 호출 횟수가 많다고 문제에서 오답처리가 되었다.

현재 코드보다 재귀 호출 횟수가 절반 정도는 되어야 한다는 것이다.

 

절반이라는 키워드에 꽂혀서 다른 방법을 찾았다.

기존에는 isEven(num - 1)의 값을 부정했는데 반대로 isEven(num - 2)의 값을 그대로 리턴하면 되겠구나 싶었다.

 

public class RecursiveExample {
	public boolean isEven(int num) {
            num = Math.abs(num);		// num값이 음수인 경우를 위해 절댓값을 쓴다.
            if(num == 0) return true;		// num이 0일때 true를 리턴한다.
            if(num == 1) return false;		// num이 1일때 false를 리턴한다.
            return isEven(num - 2);		// 호출한 재귀 함수의 값을 리턴한다. 
    }
}

 

base case로 기존에 있던 것 외에 if(num == 1) return false; 코드도 작성해주었다.
입력받은 수에서 0이나 1에 도달할 때까지 2씩 줄여 나간 뒤 0이나 1에 도달하면 그 값을 그대로 리턴하는 방법으로 바꾸었다.

숫자를 2씩 줄여나가다 보니 재귀 호출 횟수도 절반으로 줄었다. 성공적이다.

 

그리고 추가적으로 나는 매개변수가 음수인 경우를 대비해서 매개변수를 절댓값으로 바꿨는데,

다른 방법도 있어서 기록해두겠다.

 

num = Math.abs(num);
// 1번 방법. num값을 절대값으로 바꾼다.

if(num < 0) return isEven(-num);
// 2번 방법. num값이 음수이면, 값을 양수로 바꾼뒤 재귀 호출을 한다.

 

매 호출마다 절댓값으로 바꾸는 연산이 더 효율적 일지, 아니면 재귀 호출을 한번 더 하는 게 효율적 일지 고민이다. 

 

엄청 어려운 문제는 아니었지만, 이런 문제에서 헤매었기에 더욱 기록하고 싶었다.

다음 포스팅에서도 개인적으로 어려웠던 문제들을 풀어보는 글을 올릴 예정이다.

isEven 문제는 오히려 풀어서 설명하기 쉬웠는데 다음에는 어떻게 할지도 걱정이다.

슨배임들 조언 환영합니다.