이 문서는 가리사니 개발자 포럼에 올렸던 글의 백업 파일입니다. 오래된 문서가 많아 현재 상황과 맞지 않을 수 있습니다.

오늘.. 어떤 회사의 알고리즘 시험을 봤는데... 문제를 두부분이나 잘못읽고... 코딩마저 크고작은 실수하고... 결론적으로 평소에 쓰지않는 재귀를... 갑자기 쓰려니... 재귀는 무조건 역순이라는 생각을 해버리... 밤이돼서 다시 코드를 보니 한심해서 말이 안나오네요 ㅠㅠ..

회사 문제를 유출할 수 없으니 ## 재귀의 방향에 대해서만 알아봅시다. (사실 기초중에 기초인데....... C언어 처음배우면 하는거잖아요..;;;)

문제

아래 문제는 필자가 직접 낸 문제로 회사 문제와는 전혀 다른 재귀 문제입니다.

• 단일함수 / 재귀사용 / 함수내 반복문 없어야함.
• func(int num:주어진수, int res:초기값)
• 1부터 num 까지 순차적으로 덧셈
• 순차적으로 더하면서 3으로 나누어 떨어지면서 5으로 나누어 떨어지지 않는경우 해당 숫자를 곱해준다.

// 정상값 / 재귀를 사용하지않음. - 오답
public static int funcFor(int num, int res)
{
	for (int i = 1 ; i <= num ; i++)
	{
		res += i;
		if (i % 3 == 0 && i % 5 != 0)
		{
			res *= (i % 5);
		}
	}

	return res;
}

// 재귀를 역순 방향으로 호출했기 때문에 결과가 틀어짐
public static int funcError(int num, int res)
{
	if (num < 1)
	{
		return res;
	}

	res += num;

	if (num % 3 == 0 && num % 5 != 0)
	{
		res *= (num % 5);
	}

	// 스텍을 생각해보자 이미 계산이 끝났고 그 이전 숫자를 가진 함수를 부르고있다. (역순)
	return funcError(num - 1, res);
}

public static void main(String[] args)
{
	for (int i = 1 ; i <= 10 ; i++)
	{
		System.out.println("funcFor("+i+", 0) == " + funcFor(i, 0));
		System.out.println("funcError("+i+", 0) == " + funcError(i, 0));
	}
}

결과 - funcError 는 역순으로 구하면서 망함. funcFor(1, 0) == 1 funcError(1, 0) == 1 funcFor(2, 0) == 3 funcError(2, 0) == 3 funcFor(3, 0) == 18 funcError(3, 0) == 12 funcFor(4, 0) == 22 funcError(4, 0) == 24 funcFor(5, 0) == 27 funcError(5, 0) == 39 funcFor(6, 0) == 33 funcError(6, 0) == 57 funcFor(7, 0) == 40 funcError(7, 0) == 78 funcFor(8, 0) == 48 funcError(8, 0) == 102 funcFor(9, 0) == 228 funcError(9, 0) == 210 funcFor(10, 0) == 238 funcError(10, 0) == 330

이거랑은 다른 문제였지만 필자는... 문제가 재귀였음에도.... 정순으로 돌릴 생각못하고 딴생각하다가.. 반복문을 제출한 것..;; ㅠㅠ 고통받는중..;; 여러분 그래서 코딩은 안쓰는 기술이라도 가끔은 공부를 해야합니다.!!!

해결책

public static int funcAsc(int num, int res)
{
	if (num < 1)
	{
		return res;
	}

	// 해결책 : 계산을 하기전에 먼저 재귀를 호출한다.
	// 머리속에 스택을 생각해보자 이지점에서 무수히 쌓여진걸....
	// 즉, 정순으로 계산될수밖에 없다.
	// 아.... 왜 그런;; 아;; ㅠㅠㅠㄴ미ㅏ런ㅁㅇ랴32ㅓㄹ09ㅁㄴㅇ23
	int funcVal = funcAsc(num - 1, res);

	funcVal += num;

	if (num % 3 == 0 && num % 5 != 0)
	{
		funcVal *= (num % 5);
	}

	return funcVal;
}

public static void main(String[] args)
{
	for (int i = 1 ; i <= 10 ; i++)
	{
		System.out.println("funcFor("+i+", 0) == " + funcFor(i, 0));
		System.out.println("funcAsc("+i+", 0) == " + funcAsc(i, 0));
		System.out.println("funcError("+i+", 0) == " + funcError(i, 0));
	}
}

결과 funcFor(1, 0) == 1 funcAsc(1, 0) == 1 funcError(1, 0) == 1 funcFor(2, 0) == 3 funcAsc(2, 0) == 3 funcError(2, 0) == 3 funcFor(3, 0) == 18 funcAsc(3, 0) == 18 funcError(3, 0) == 12 funcFor(4, 0) == 22 funcAsc(4, 0) == 22 funcError(4, 0) == 24 funcFor(5, 0) == 27 funcAsc(5, 0) == 27 funcError(5, 0) == 39 funcFor(6, 0) == 33 funcAsc(6, 0) == 33 funcError(6, 0) == 57 funcFor(7, 0) == 40 funcAsc(7, 0) == 40 funcError(7, 0) == 78 funcFor(8, 0) == 48 funcAsc(8, 0) == 48 funcError(8, 0) == 102 funcFor(9, 0) == 228 funcAsc(9, 0) == 228 funcError(9, 0) == 210 funcFor(10, 0) == 238 funcAsc(10, 0) == 238 funcError(10, 0) == 330

결론

여러분.. 알고리즘 시험이 있을때 필자처럼... 공부안하고 그냥 보면 안돼요... 초딩도 풀만한 문제(사실 C언어 처음배울때나 하는거잖아요... ㅠㅠ)를 틀려서 정신이 붕괴된...