16. 재귀함수 피보나치

재귀함수로 팩토리얼 구현하기

# 파이썬 코드입니다.
int Factorial_recursion(int num) {

	if (num == 1) {
		return 1;
	}

	return num * Factorial_recursion(num - 1);

}

• 이해를 바탕으로 보면: 재귀함수가 호출되고 숫자가 들어감 ex) 5 --> 5 (4가 들어간 재귀함수가 호출됨) --> 5 4 (3이 들어간 재귀함수가 호출됨) --> 5 4 3 (2가 들어간 재귀함수가 호출됨)...

• stack은 f(5), f(4), f(3)... 이렇게 계속 쌓일거임

• 계속 호출되다가 _num이 1이 되면? --> 그때는 그냥 1을 반환해주면 재귀함수의 호출이 중단됨 --> 그럼 지금까지 쌓인 5 4 3 2에 1이 return되어서 최종값이 return되는거임

재귀함수로 피보나치 수열 구현하기

• 먼저 반복문

// 1 1 2 3 5 8...
int fibonacci_for(int _number) {

	int count = 1;
	int pre_count = 1;
	int result = 0;

	if (_number <= 2)
	{
		return 1;
	} 
	else
	{
    	// 반복횟수는
		for (int i = 0; i < _number - 2; i++)
		{
			result = pre_count + count;
            // 현재 숫자를 이전 숫자에 넣어줌
			pre_count = count;
            // 결과값이 현재 숫자가 됨 (한 칸씩 전진)
			count = result;
		}
		return result;
	}
}

• 재귀함수 버전

// 피보나치 수열
// 1 1 2 3 5 8...
int fibonacci_recursion(int number) {
	if (number <= 2) {
		return 1;
	}

	// 이렇게 된 이유는 피보나치 n번째의 수는 (n - 1)번째수 + (n - 2)번째수 이기 때문임
	return fibonacci_recursion(number - 1) + fibonacci_recursion(number - 2);
} // 엄청나게 간결해짐

• 원리는 아까랑 비슷함, 계속 돌다가? number - 1 <= 2, number - 2 <= 2이 되는 순간 각각 1을 반환한거임

하지만 위의 피보나치 수열은 치명적인 문제가 있음

• 바로 속도, 60번째 정도를 호출하면 일주일이 걸릴 수도 있음, tree 구조를 보면 호출수에 따라 $O(2^n)$으로 증가하는 것이 보임

• 5가 나와야하면 1이 5개, 8이 나와야 하면 1이 8개 이렇게 나와주는거 같음 큰 수끼리 더해서 큰 수를 만드는게 아니라 분기가 계속 갈리고 그 모든 분기 (숫자 1)들이 전부 더해지면서 큰 수를 만들기 때문에 속도가 느린거 같음

• 따라서 개선이 필요함 --> 너무 느려서 재귀를 쓰는건 바람직하지 않지만 굳이 사용한다면 꼬리재귀 등을 사용할 수 있음