1.재귀함수란?
-자기자신을 호출하는것,완료되지 않는 함수를 호출하는 것
2.재귀함수의 흐름
하지만 ,이렇게 호출을 계속해서 복사본을 만들다보면, 무한 루프 상태에 걸리기때문에
함수안에 기저조건(=탈출조건)을 올바르게 구현하여 특정한시점에 함수를 반환시켜 종료시키면된다.
3.재귀함수를 쓰는 이유
주로, 복잡한 식을 간단하게 구현하기 위해 재귀함수를 씁니다.
활용> [피보나치 수열] : 호출순서를 추적하기는 힘드나, 호출 관계를 파악함으로써 간단하게 구현을 구현할수 있다.
0,1, 1,2,3,5,8,13,21 ....
수열의 n번째 값 = 수열의 n-1번째 값+ 수열의 n-2번째 값
fib(n)
{
0-------n=1
1-------n=2
2-------n이 1 또는 2가 아니라면
}
//수열의 관계를 파악한뒤 코드로 구현해보자!
int fib(int n)
{
if(n==1)return 0; //재귀의 탈출조건
else if(n==2)return 1; //재귀의 탈출조건
else return fib(n-1)+fib(n-2); //매개변수를 바꿔 다시 호출한다.
}
int main()
{
cout<<fib(5)<<endl;
//피보나치수열의 5번째 숫자를 알고싶을때
}
<흐름이해하기> 그림을 그려서 이해하면 쉽다!
4.재귀함수의 주의할점
-Stack Overflow
실제 프로그램안에서 재귀호출이 얼마나 일어나게 될지 짐작하기 어렵다.
1부터 100000까지 total 구하기
for문 : 에러 X
재귀함수:에러 발생
차이점: 함수 호출의 차이
=>함수가 호출될때 스택메모리를 사용하게 됩니다.
재귀호출은 완료되지않는 함수가 꼬리를 물며 계속해서 호출되어 실행되기때문에 메모리에 쌓이게 된다.
계속해서 호출되버리면 메모리가 부족해져서 에러가 발생하게 됩니다.
그렇기 때문에 재귀함수를 사용할때 호출을 제한하거나 반복문으로 대체하여 사용하는 것이 바람직합니다.
5.반복문과 재귀함수의 차이
-재귀와 반복은 같은문제를 해결할수있다.
그러나 재귀방법이 적은코드를 사용해 효율적으로 처리가 가능합니다.
*반복문: 함수의 호출은 매개변수 리스트를 보관할 메모리영역과 메소드를 실행할수 있는 복사공간이 필요하다.
반복적인 메소드 호출을 위한 메모리는 한번만 필요하기때문에 성능적인 면에서는 유리하다.
*재귀: 함수 호출시 메모리를 위한 비용과, CPU사용 시간이 더 많이 소요됨 , 계속해서 복사하면서 CPU에서 처리하기때문에
하지만 코드를 이해하고 유지하는 것이 중요하다면 재귀를 이용한다고 한다.
