자료구조/알고리즘 - 재귀 함수

1.재귀 함수(recursion function) : 자기 자신을 호출하는 함수
 -재귀 : 원래의 자리로 되돌아가거나 되돌아옴

 -장점
  (1)여러개의 반복문을 불필요하게 사용하지 않기 때문에, 코드 간결화 및 수정이 용이함
  (2)변수를 여러개 사용할 필요가 없음

 -단점
  (1)코드의 흐름을 직관적으로 파악하기 힘듦(가시성down)
  (2)반복문에 비해 더 많은 메모리 사용(재귀함수는 반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하기 때문)
  (3)메서드가 종료된 후 복귀를 위한 컨텍스트 스위칭 비용 발생(컨텍스트 스위칭이 너무 잦으면 오버헤드가 발생하여 성능이 떨어짐)
   *비용이 높음 = 오버헤드 발생

 -재귀를 사용하기 적합한 경우
  (1)주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  (2)중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
   *"3번 이상 nesting 된 코드는 똥이다" - Linux kernel coding style guide
  (3)변수 사용을 줄여서 프로그램 오류가 발생할 가능성을 줄이고자 할 경우(=변경 가능한 상태(mutable state) 제거)


 -재귀적 사고 guide

  (1)재귀 함수의 입력값과 출력값 정의하기(문제를 가장 추상적으로 또는, 가장 단순하게 정의)

  (2)문제를 쪼개고 경우의 수 나누기
    -문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분(일반적인 경우 입력값으로 이 기준을 정함)
    -구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것
    -경우의 수를 모두 나누면, 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 구분됨

  (3)단순한 문제 해결하기
    -가장 쉬운 문제 해결(=재귀의 기초(base case))
     *base case는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성함

  (4)복잡한 문제 해결하기

  (5)코드 구현하기