재귀함수. Recursive function.

재귀함수에 대해서 인터넷에 정의는 많은데 도대체 어떻게 만들면 되는지 설명이 있는 곳이 별로 없어서 몇 글자 끄적여 봅니다.

알고보면 별로 어렵진 않아요.

가장 유명한 예제인 n! 부터 예를 들도록 해보겠습니다.

n! 를 수식으로 펼쳐보면 다음과 같습니다.

머리가 아파오지만 참고 봅시다.

저도 수학 별로 안 좋아합니다.

기호로 보면 복잡하니까 n! 를 f(n)으로 바꿔봅시다.

이게 더 복잡해 보일 수도 있지만, 아래와 같이 정리를 하기가 쉽습니다.

여기서 제일 중요한 부분은

입니다.

왜 중요하냐면 저 부분이 바로 재귀함수의 종료 조건이기 때문입니다.

재귀함수라는게 계속 자기를 부르는 거라 이게 언젠가는 끝나야 되는데 그 끝나는 조건을 지정하는게 재귀함수를 만들 때 가장 큰 일입니다.

이 것만 한다면 재귀함수는 거의 다 끝났다고 봐도 됩니다.

그럼 C코드로 함수를 만들어 봅시다.

일단 아래와 같이 함수를 만든다고 가정해봅시다.

int f(n)
{
}

쉽죠?

이제 재귀함수의 종료 조건을 넣어 봅시다.

n 이 1일 때 이 함수는 종료됩니다.

int f(n)
{
    if (n == 1) {
        return 1;
    }
}

종료조건을 정했으면 나머지는 쉽습니다.

f(n) 의 조건을 따라서 나머지 부분을 한 번 채워봅시다.

앞에서

f(n) = n * f(n - 1)

이라고 알아냈습니다. 그러니까 이 값을 return 하면 됩니다.

int f(n)
{
    if (n == 1) {
        return 1;
    }
    
    else {
        return n * f(n - 1);
    }
}

물론 재귀함수는 그냥 조건문으로 바꿀 수도 있지만 재귀함수가 이해하기도, 구현하기도 쉬울 때가 많이 있습니다.

n! 야 인터넷에 널리고 널린 예제니 다른 예제로 해봅시다.

---

간단한 숫자야구게임으로 해봅시다.

숫자야구게임의 규칙은 아래와 같습니다.

1. 1 ~ 9까지의 숫자 중 한글자씩 골라 총 세 자리의 수를 만듭니다 (예 : 586)
2. 이제 이 숫자를 짐작해서 세 자리 수를 추측해 봅니다 (예 : 256)
3. 정답과 일치하는 숫자가 자리까지 일치하면 스트라이크로 셉니다 (예 : 1 스트라이크 - 256)
4. 정답과 일치하는 숫자가 자리는 다르다면 볼로 셉니다(예 : 1볼 - 256)
5. 만약 숫자가 모두 일치하지 않는다면 아웃으로 셉니다

숫자야구를 잘 하는 방법은 여러가지가 있겠지만, 우리는 무식하게 작동하긴 하지만 속도는 똥마려운 강아지마냥 재빠른 컴퓨터란 놈을 사용하므로 그냥 하나하나 다 대입하는 걸로 해결을 봅시다.

즉, 우리가 하고자 하는 방법은 아래와 같습니다.

1. 세 자리 숫자 각각에 1 ~ 9까지의 숫자를 대입합니다.
2. 정답과 일치하는지 확인 후 맞다면 정답이므로 할 일을 다 끝냅니다.
3. 오답이라면 다시 다음 숫자를 대입해 정답을 검사 해봅니다.

어떻게 하려고 하는지는 대충 감이 오실 겁니다.

원래대로라면 세 자리에 동일한 숫자는 올 수 없으나 그런 건 신경쓰지 맙시다.

자료구조를 일단 만들어 봅시다.

정답을 right_answer[3] 으로 우리가 추측하는 답을 a[3] 이라고 가정합시다.

그러면 아래와 같이 정답인지 아닌지 결정하는 함수를 만들 수 있습니다.

#define TRUE	(1)
#define	FALSE	(-1)

int check_answer(int a[3], int right_answer[3])
{
	int i = 0;

	for (i = 0 ; i < 3 ; i++)
	{
		if (a[i] != right_answer[i]) {
			return FALSE;
		}
	}

	return TRUE;
}

그럼 본격적으로 재귀함수를 만들어 봅시다.

위에서 밝혔 듯이 하고 싶은 건 단순합니다.

차례대로 숫자를 1 ~ 9 까지 대입 해 보는 거죠.

함수의 기본 구조를 만들어 봅시다.

배열을 사용하는 것이니 index 를 지정해줘야 겠고, 우리가 추측하는 a[]를 인자로 넘겨줘야겠죠.

int guess_number(int index, int a[3], int right_answer[3])
{
}

이름은 이렇게 정해놓고, 가장 처음 이 함수를 부를 때는 이렇게 부르기로 합니다.

guess_number(0, a, right_answer);

처음부터 시작하니까 0 부터 출발합니다.

단순합니다. index 0 부터 2 까지(즉 a[0] ~ a[2] 에) 각자 숫자를 1 ~9 까지 채워놓고 값을 각각 비교 해보는 겁니다.

재귀 함수를 잠깐 생각해봅시다.

저 index 를 하나씩 늘리면서 함수를 불러주면 될 것 같습니다.

int guess_number(int index, int a[3], int right_answer[3])
{
	/* TODO : something */
	guess_number(index + 1, a, right_answer);
}

그럼 일단 종료조건을 생각 해봅시다.

a[2] 까지 숫자를 채워넣고 난 뒤, 위에서 만들어 놓은 check_answer() 를 불러서 확인한 후 정답인지 오답인지를 return 해주면 됩니다.

a[2] 까지 채워넣었다면 index 는 3이 되겠죠.

return 값을 받기 위한 ret 변수를 선언하고 아래와 같이 꾸밉니다.

int guess_number(int index, int a[3], int right_answer[3])
{
	int ret = 0;

	if (index == 3) {
		ret = check_answer(a, right_answer);
		return ret;
	}

	/* TODO : something */
	guess_number(index + 1, a, right_answer);
}

위에서 적어놨던 절차를 따르는 겁니다.

자, 그럼 index 가 3이 아닐 때 아래쪽에 재귀 함수를 호출하면 될 것 같습니다.

int guess_number(int index, int a[3], int right_answer[3])
{
	int ret = 0;

	if (index == 3) {
		ret = check_answer(a, right_answer);
		return ret;
	}

	else {
		/* TODO : something */
		guess_number(index + 1, a, right_answer);
	}
}

저 TODO 부분을 채워봅시다.

1 ~ 9 까지 하나씩 채우는 겁니다.

for 문을 돌리면서,

a[index] 에 1 ~ 9 까지 하나씩 채워넣으면 됩니다.

int guess_number(int index, int a[3], int right_answer[3])
{
	int ret = 0;
	int i = 0;

	if (index == 3) {
		ret = check_answer(a, right_answer);
		return ret;
	}

	else {
		for (i = 1 ; i < 10 ; i++)
		{
			a[index] = i;

			ret = guess_number(index + 1, a, right_answer);
			if (ret == TRUE){
				return ret;
			}
		}
	}
}

호출하는 재귀함수가 TRUE 를 return 하면 숫자를 다 찾았다는 의미이므로 TRUE 를 return 하고 끝을 내면 됩니다.

별거 아닌 글을 너무 오래 썼네요.