팩토리얼 예제

이 예제를 풀면서 시간이 오래걸린 이유는 변수를 몇개 할당해야 하는지 감을 잡지 못해서 인듯.

루프문으로 주어진 문제를 풀려면 내생각엔

1. 곱셈할 횟수를 담을 변수(n!일 경우 n+1번) = 루프문을 동작시킬 횟수(i)
2. 실제로 결과가 들어갈 변수
3. 사용자로부터 입력을 받을 변수

총 세개가 필요한거 아닐까? ..하지만 계속 두개로도 가능해보인거 같음..

long loop_factorial(int n)
{
	/*long sol = n;
	if (n == 0)
	{
		sol = 1;
	}
	else
	{
		for (int i = n; i != 1; i--)
		{
			sol *= (i - 1);
		}
	}
	
	return sol;*/

	long ans;

	for (ans = 1; n > 1; n--)
		ans *= n;

	return ans;
}

루프문을 이용한 팩토리얼구하는 함수 예제

주석처리된건 내가 만든거고 아래는 홍정모님이 만든 코드임. 나는 n값이 0인경우와 아닌경우를 굳이 나눴는데, 홍정모의 코드는 애초에 for문안에서 ans=1로 할당하고, n==0인경우는 for문을 작동하지 않게해서 이 부분을 간단하게 줄여버림…그리고 역시 변수는 두개만 필요했음. 1과 3은 같은 것임.

재귀함수를 이용한 팩토리얼구하는 함수 예제

long recursive_factorial(int n)
{
	/*int sol = n;
	if (n == 0)
	{
		sol = 1;
	}
	else 
	{
		if (n != 0)
		{
			sol = sol * (n - 1);
			recursive_factorial(sol);
		}
	}
	return sol;*/

	if (n > 0)
	{
		return n * recursive_factorial(n-1);
	}
	else
		return 1;
}

이번에도 홍정모님의 코드는 엄청 간단했음. 나는 구현실패… 재귀함수에 대한 이해가 아직 부족한듯.

그리고 위처럼 return 바로 뒤에다가 재귀호출을 하는것을 tail recursion혹은 end recursion이라고 함. 이렇게 짜는게 가장 깔끔하고 수학적인 알고리즘을 구현하는데 가장 알맞다고 한다.

내가 tail recursion에 대한 이해가 부족했던건 tail recursion을 하면 결과값을 담을 변수가 굳이 필요없다는 걸 알지 못해서였던 것 같음. 한줄씩 빌드를 해보니 재귀함수를 이용한 팩토리얼구하는 방식에서는 stop condtion에 걸리기 전까지 계속 return하려고 하지만 tail recurion이라서 값이 콘솔에 출력되지 않음. 그러다가 stop condition걸리자마자 걸렸을때의 return을 출력하는데, 그게 우리가 원하는 값임.

• 여기서 드는 생각은, 반환값을 담는 메모리 공간은 우리가 선언한 변수처럼 눈에 보이는건 아니지만 여전히 존재하고, tail recursion을 사용할때는 그 보이지 않는 메모리공간을 이용해서 값을 출력한다는 점임. 그래서 루프문을 사용했을때보다 선언되는 변수가 하나 줄음. 이점을 기억하고 tail recursion을 활용하자!!!