220325(1)_함수(4)_함수의 재귀(Recursion)

#include <iostream>

/*
재귀함수 : 함수 안에서 자기 자신을 호출하는 함수를 말한다.
재귀함수를 사용할때는 반드시 종료부분을 만들어 주어야 한다.
재귀함수를 종료한다는 것은 더이상 자기자신을 호출하는 것을 막아누즌 것이다.


ex)자기 자신을 3번 호출하는 재귀함수
Output시작	스택생성
		Output시작	스택생성
				Output시작	스택생성
				Output끝		스택정리
		Output끝		스택정리
Output끝		스택정리

이게 무한으로 반복되면 Output이 끝나서 스택이 정리가 되지 않는다.
그럼 메모리 안의 스택 공간에 계속 생성된 함수의 스택만 쌓이므로 결국 꽉 차게 되고,
오류가 발생하게 된다.
이것을 스택 오버플로우라고 한다.


*/
/* ↓
void Output()
{
	Output();
}
*/


//cf)모든 반복문은 재귀함수로 구현할 수 있다.
//코드가 간결해지지만, 속도가 느려진다는 단점이 존재한다.
//재귀 과정에서 스택을 생성하고, 함수의 인자를 전달해주는 과정이 없기 때문
//선생님은 개인적으로는 위의 이유들 때문에 선호하지 않는다고 한다.

//재귀함수의 대표적인 예: 팩토리얼
int Factorial(int Number)
{
	if (Number == 1)
		return 1;
	return Number * Factorial(Number - 1);
}
//근데 이런식으로 만들면 계속 함수호출과 스택생성이 반복되어
//공간이 심하게 소모된다는 단점이 있다.
//먼저 호출된 재귀함수가, return문에서 나중에 생성된 재귀함수의 결과가 들어올 때까지 기다리고 있는 것이다.



//꼬리 재귀
///그 해결법으로, '꼬리 달기'라는 방법이 있다.
///Result 인자까지 전달해줌으로써 공간 낭비를 줄인다.

///재귀와 꼬리 재귀의 큰 차이는 다음 호출을 위한 파라미터의 연산이 어디서 일어나는가이다.
///즉, return문에 연산이 있냐 없냐의 차이이다.
///return문에 연산이 존재하지 않으므로, 스택에 연산을 위한 공간을 만들어두고 기다리고 있지 않아도 된다.
///그러므로 공간이 절약되는 장점이 있다.
int FactorialTail(int Number, int Result = 1)
{
	if (Number == 1)
		return Result;
	return FactorialTail(Number - 1, Number * Result);
}
//꼬리재귀를 통한 최적화를 사용하기 위해선
//프로젝트 우클릭 - 옵션 - C/C++ - 최적화에서 '최적화(속도 우선)'을 선택
//실제로 이렇게 코드를 작성했을 때, 위 옵션을 사용할 경우 컴파일러가 아예 do-while문으로 코드를 인식하여 컴파일한다고 한다.

//근데 꼬리재귀 쓸 바에는 while문이나 for문을 이용하여 사용한다.
//가끔 회사에서 필기시험 볼 때 손코딩 시키는 회사들도 있는데
//그런 곳에서 가끔 꼬리재귀를 물어보기도 한다.
//재귀와 꼬리재귀의 차이를 물어보기도 함.



//재귀와 꼬리재귀로 만들어 보는 피보나치 수열
//0,1,1,2,3,5,8,
//첫번쨰 수열 = 0, 두번째수열 = 1
// 
//F(N)의 규칙
//N = 0 F(N) = 0
//N = 1 F(N) = 1
//N > 1 F(N) = F(N-1) + F(N-2)
int Fibonacci(int Trials)
{
	if (0 == Trials)
		return 0;
	else if (1 == Trials)
		return 1;
	else
		return Fibonacci(Trials - 1) + Fibonacci(Trials - 2);
}


int FibonacciTail(int Number1, int Number2, int Trials)
{
	if (1 == Trials)
		return Number2;

	return FibonacciTail(Number2, (Number1 + Number2), --Trials);
}



int main()
{

	std::cout << "팩토리얼 재귀함수: " << Factorial(5) << std::endl;
	std::cout << "팩토리얼 꼬리재귀: " << FactorialTail(5) << std::endl;

	std::cout << "피보나치 재귀함수 : " << Fibonacci(20) << std::endl;
	std::cout << "피보나치 꼬리재귀 : " << FibonacciTail(0, 1, 20) << std::endl;
	//실제로 코드를 실행해보면 10단위 이상에서 
	//피보나치 재귀함수와 꼬리재귀함수의 계산속도가 차이가 나는 것을 알 수 있다.



	return 0;
}