[C++] 재귀함수

재귀함수 - 함수 안에서 자기 자신을 호출하는 함수

자기 함수 내에서 자기 자신과 동일한 함수를 호출하는 형태 

반드시 탈출 조건이 있어야 한다!!!!

 

재귀함수는 가독성, 구현의 용이

 

※ 잘못 사용하면 Stack overflow라는 오류가 발생할 수 있다.

 

팩토리얼 함수

int Factorial(int _iNum){
   int iValue = 1;
   
   for(int j=0; j< _iNum-1; ++j){
      iValue *= (j+2);
   }
   
   Factorial(10);   //재귀함수
   
   return iValue;
  }

 

재귀함수를 이용하여 팩토리얼을 구현해보자.

10!을 구해보면

10! = 10 X 9! 이랑 같다. 이를 계속 적용해보면,

10! = 10*9! = 10*9*8! = 10*9*8*7! ...

팩토리얼 재귀함수로 구현할 때 메모리 영역

return을 만나면 함수 종료된다. →  값 넘겨줌

이 부분을 코드로 나타내면 다음과 같다.

int Factorial_Re(int _iNum){

  if(_iNum == 1){   
     return 1;    //재귀함수 종료
  }
  
  return _iNum * Fatorial_Re(_iNum-1);   
  //함수가 종료되면서 쌓여있던 메모리 영역 사라지고 리턴값으로 넘겨준다.
}

int main(){
   
   int iValue = Factorial_Re(10);   //함수호출

  return 0;
}

 

피보나치 수열

1 1 2 3 5 8 13 21 34 55 ...

1번째 숫자와 2번째 숫자는 고정이다.

3번째 숫자를 구하기 위해서는 1번의 덧셈을 진행해야 한다.

4번째 숫자를 구하기 위해서는 2번의 덧셈을 진행해야 한다.

5번째 숫자를 구하기 위해서는 3번의 덧셈을 진행해야 한다.

...

10번째 숫자를 구하기 위해서는 8번의 덧셈을 진행해야 한다.

 

즉 n번째 숫자를 구하기 위해서는 n-2번의 반복문을 실행해야 한다.

 

그리고 더해질 2개의 숫자와 두 숫자를 더한 값이 들어갈 메모리 공간을 만들어줘야 한다.

 

첫번째 덧셈 실행 후 "두번째 숫자(iPrev2)"은 "첫번째 숫자(iPrev1)" 영역으로 가고 더해서 나온 값(iValue)는 두번째 숫자 영역(iPrev2)에 저장된다. 이 실행이 반복문에 의해서 원하는 값이 나올 때까지 반복된다!

 

int Fibonacci(int _iNum){
   if(_iNum == 1 || _iNum ==2){
      return 1;      
   }
   int iPrev1 = 1;     //메모리 공간 만들어주기
   int iPrev2 = 1;
   int iValue = 0;
   
   for(int i = 0; i < _iNum -2; ++i){
      iValue = iPrev1 + iPrev2;
      iPrev1 = iPrev2;
      iPrev2 = iValue;
      }
    return iValue;
 }
 
 int main() {
 
    int iValue = Fibonacci(3);
    
 }

이번에 피보나치 수열을 재귀함수를 이용해서 구해보자.

10번째의 숫자는 8번째 숫자와 9번째 숫자의 합이다.

int Fibonacci_Re(int _iNum){
   if(_iNum == 1 || _iNum ==2){
      return 1;        //재귀함수 탈출조건
   }
    return Fibonacci_Re(int _iNum-1) + Fibonacci_Re(int _iNum-2);
 }
 
 int main() {
 
    int iValue = Fibonacci_Re(5);
    
 }

계속 함수를 호출하여 함수가 쌓여가다가 return 값을 만나면서 함수가 종료되고 그 return 값들을 돌려주는 방식으로 진행됨.

(쭉쭉 함수가 쌓이면서 올라갔다가 return 값 만나면서 거꾸로 내려오는 느낌!!!)

계산이 굉장히 오래걸린다는 문제가 있다!! 2^n배의 함수를 호출하므로.. - 함부로 막 사용하면 안된다!

 

재귀함수는 계층구조를 표현해야할 때 사용하기 좋다!