재귀함수(Recursion) 한번에 이해하기

1. 재귀함수(Recursion)의 정의
   • 재귀함수의 재귀는 한자로 두번 재에 돌아올 귀자를 써서 再歸 라고 표현됩니다. 영어로는 Recursion이라고 표현합니다.
   • 실제 코드에서는 어떤 함수 안에서 그함수 자신을 호출하는 함수를 재귀함수(Recursion)라고 표현합니다.
2. 재귀함수 구현방법
   1. 재귀함수의 요건
      1. 종료조건(기저조건)
         • 재귀함수에서 필수적인 요소가 바로 종료조건입니다. 아래 코드에서 종료조건이라고 주석처리한 라인이 없다면 무한히 루프를 돌다가 결국 스택오버플로우를 일으키고 프로그램이 죽습니다. 그래서 어느 조건에 도달하면 이 함수를 끝낸다는종료조건을 넣어주어야 합니다.

           func recursive(){
           	func recursive()
               if(종료조건) //종료조건
               	return   //종료조건
           }​

            
      2. 분할정복
         • 재귀함수를 구현하는 가장 큰 이유가 바로 분할정복입니다.
         • 대부분의 재귀함수는 반복문으로도 구현이 가능합니다. 그러나 분할정복에서만은 반복문 돌리는 것보다 재귀함수로 구현하는 방법이 훨씬 큰 이점을 취할 수 있습니다.
         • 예를 들면 아래 코드와 같이 자기자신 안에 자기자신을 두번씩 호출합니다. 이 함수를 기준으로 설명하면 0보다 작은 값이라는 최소 단위까지 분할한 뒤 합산하면서 정복해나가게 됩니다.

           recursive(int n){
           	if(n <= 0)
               	return 1
               return recursive(n-1) + recursive(n-2)
           }​

   2. 재귀함수의 장점
      • 앞서 말한 것과 같이 재귀함수는 대부분 반복문으로 구현이 가능합니다. 다만 보다 간략하게 구현할 수 있는 경우가 상당히 많습니다.
   3. 재귀함수의 단점
      • 재귀함수의 단점은 위에서 설명한 스택오버플로우에 걸릴 가능성이 높다는 점입니다.
      • 재귀함수의 특성상 함수 내부에서 계속해서 스택에 함수를 올리면서 동작하기 때문에 너무 많이 호출하게 되면 컴퓨터가 감당하지 못하면서 오버플로우를 내게 됩니다.
3. 재귀함수의 쓰임
   1. 퀵소트 등 분할해서 정렬하는 정렬 방식
   2. 고속 푸리에 변환
   3. 카라추바 알고리즘
4. 정리
   • 재귀함수는 잘 사용한다면 어려운 로직을 간단하고 명료하게 구현할 수 있습니다.
   • 다만 남발한다면 컴퓨터에 큰 부하를 가져올 수 있고 스택 오버플로우 등의 시스템 에러를 초래할 수 있습니다.