봄이네집의 일고리즘 - 2) 재귀함수 심화 및 응용

지난시간에 이어 재귀함수 심화입니다.

우리는 지난 시간에 재귀함수의 개념에 대해 알아봤습니다. 재귀 함수의 개념, 재귀 함수가 쓰이는 이유, 그리고 간단한 재귀함수 예제 두 문제를 풀어봤습니다.

재귀함수가 의미있는 결과값을 돌려주려면 아래의 조건이 성립해야 함을 이해했습니다.

  • 재귀 호출을 일으키지 않는 기본 케이스(base case)가 존재해야 합니다.
  • 자기 자신을 반복 수행하며 결과값을 도출하는 재귀 케이스(recursive case)가 존재해야 합니다.

이러한 이해를 바탕으로, 오늘은 재밌는 예제 하나와 뒷골 잡는 예제 몇 개를 더 풀어보고자 합니다.

사딸라

사딸라를 아시나요?

김두한: 1달러는 너무 적소. 4딸라쯤 합시다.
미군: 비웃음
김종원(한국군 계엄사령관): 4딸라?
김두한: 4딸라. 일급 사딸라로 합시다.
김종원: 어떻게 1딸라 임금을 네 배나 올린단 말이요? 1.5 딸라 합시다.
김두한: 사딸라.
…(4달러가 될 때까지 반복)…

김두한은 결국 4 달러의 일급을 쟁취해 냅니다. 협상 과정에 논리나 데이터는 없었습니다. 김두한은 계속 사딸라를 외쳤고, 무슨 이유에선지(…) 미군과 한국군 계엄사령관이 점차 금액을 높여 주다가 김두한이 목표한 4달러에 이르자 김두한이 “오케이, 땡큐! 오케이, 사딸라!” 를 외치며 협상이 종료됩니다.

이 우스꽝스럽기 그지 없는 협상 과정을 우리는 재귀함수로 풀어보고자 합니다. 알아요 쓸데 없는 짓인거…. 뭐 어때요. 공부하는 입장인데 재밌게 공부하면 좋죠.

아래의 코드를 봐 주세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class SaDdala{

	private static final String INTRO = "일급 1달라는 너무 적소, 4딸라. 4딸라로 합시다.";
	int dollar = 1;

	public static void main(String args[]){
		SaDdala sd = new SaDdala();
		System.out.println(INTRO);
		sd.FourDollars();
	}

	public void FourDollars(){
		if (dollar == 4){
			System.out.println("can't help with this. alright. four dollars!");
			System.out.println("오케이, 사딸라. 땡큐, 사딸라!");
		}

		else{
			System.out.println(dollar + " dollars.");
			System.out.println("사딸라.");
			dollar++;
			FourDollars();
		}
	}
}

이 반복문스러운 협상은 김두한의 목표 금액인 4딸라를 쟁취하면 끝나야하기 때문에, base case는 dollar == 4 로 잡았습니다. 슬금슬금 늘어나던 일급이 사딸라에 이르면 미군의 탄식과 김두한의 환호를 콘솔에 출력하고 재귀 함수는 종료됩니다.

recursive case에서는 시시각각 상승하는 일급을 콘솔에 찍어주고, int dollar의 값을 하나 높여준 후 자기 자신을 다시 호출합니다. 단 이미 일급이 사딸라에 도달했다면 이 recursive case는 실행되지 않을 것입니다.

이진수 구하기

이진수가 뭔지 기억이 잘 안 난다구요? 괜찮아요.

0과 1이라는 두 개의 숫자만을 사용하여 수를 나타내는 진법.

ㅋㅋㅋㅋㅋ 별 도움이 안 될것 같습니다.
표기는 오른쪽에서부터 1, 2, 2의 제곱, 2의 세 제곱…이런 식으로 주욱 늘어집니다.
예를 들어…

숫자 ‘10’ 은 23 + 2 이므로 1010(2)입니다.
숫자 ‘7’ 은 22 + 2 + 1 이므로 111(2)입니다.

이해가 가시는지….

베이스 케이스 구상하기

우리는 ‘1’ 과 ‘0’ 의 표현에 주목할 필요가 있습니다. 만약 함수로 1이나 0이 투입된다면, 자기 자신을 그대로 돌려주면 됩니다. 숫자 ‘7’의 표현 사례를 다시 봐 주세요.

베이스 케이스는 1 이하의 숫자가 들어오면, 자기 자신을 리턴해주는 것으로 표현할 겁니다. n <= 1 return n;이 되겠죠?

재귀 케이스 구상하기

다음 자릿수를 계속해서 표현해 주려면, 일단 n / 2의 값을 파라메터로 재귀 호출해야 합니다. 이번 자릿수에는 자기 자신을 2로 나눈 나머지, 즉 n % 2를 돌려주면 될 겁니다.

아래 코드처럼 구현해 보았습니다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class BinaryConverter{
	
	public static void main (String args[]){
		binary(10);
	}

	public static void binary(int n){
		if (n < 2){
			System.out.print(n);
		}

		else{
			binary(n / 2);
			System.out.print(n % 2);
		}
	}
}

어때요. 참 쉽죠?

오늘 내용도 마찬가지로 제 깃헙 리포지토리에 모든 구현 내용이 올려져 있습니다.

즐거운 재귀함수 공부는 내일 끝납니다. 앞으로 더 어려운 알고리즘 기법들이 우리를 기다리고 있읍니다. ㅋㅋㅋㅋㅋㅋ 망했네요.

즐겁게 알고리즘 공부합시다! 고맙습니다.