재귀 함수

재귀의 개념

• 재귀 : 원래의 자리로 되돌아가거나 되돌아옴
• 재귀(recursion)
  • 어떤 문제가 있을 때, 그 문제를 동일한 구조의 더 작은 문제로 나눌 수 있고, 이 작은 문제를 해결함으로써 전체 문제를 해결하는 방법
  • 재귀를 사용한 코드는 대부분의 경우 간결하고, 이해하기 쉽다
• 재귀 함수
  • 자기 자신을 호출하는 함수
  • 재귀 함수를 잘 이용한다면 반복적인 작업을 할 때 문제를 좀 더 간결한 코드로 풀어낼 수 있다

재귀 함수의 장점

1. 코드가 간결해지고 수정이 용이하다
   • 불필요하게 여러 개의 반복문을 사용하지 않는다
2. 변수를 여러 개 사용할 필요가 없다

재귀 함수의 단점

1. 반복문에 비해 코드의 흐름을 직관적으로 파악하기 어렵다
2. 반복문에 비해 메모리를 더 많이 사용하게 된다
   • 메서드를 호출하면 지역 변수, 매개 변수, 반환값 등을 모두 process stack에 저장하게 되는데, 반복해서 메서드를 호출하면 이러한 값들이 많이 저장되어 메모리를 많이 사용하게 된다
3. 메서드를 호출하고 메서드가 종료된 후에 복귀를 위한 컨텍스트 스위칭 비용이 발생한다

재귀 함수 사용을 위한 조건

1. 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 한다
2. 재귀 호출이 종료되는 시점이 존재해야 한다

재귀가 적합한 경우

1. 주어진 문제를 비슷한 구조의 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
3. 변수 사용을 줄여 mutable state(변경 가능한 상태)를 제거하여 프로그램 오류 발생 가능성을 줄이는 경우

재귀의 과정

1. 문제를 좀 더 작게 쪼갠다
2. 문제가 더는 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갠다
3. 가장 작은 단위의 문제를 해결함으로서 전체 문제를 해결한다

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기
   • 도달하고자 하는 목표(풀고자 하는 문제)를 정의하는 데에 도움이 된다
   • 문제를 가장 추상적으로 / 단순하게 정의해야 한다
     • 이 때, 어떤 것을 입력값으로 받고 어떤 것을 출력하는지 생각해본다
2. 문제를 쪼개고 경우의 수를 나누기
   • 문제를 쪼갤 때는 쪼갤 기준을 정하고, 그 기준에 따라 문제를 큰 경우와 작은 경우로 구분할 수 있는지 확인한다
     • 일반적인 경우, 입력값으로 이 기준을 정한다
     • 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 매길 수 있다면 문제를 구분하는 데에 도움이 된다
     • 구분된 문제를 푸는 방식이 순서나 크기와 관계 없이 모두 같다면, 문제를 제대로 구분한 것이다
   • 문제에서 주어진 입력값에 따라 경우의 수를 나눈다
     • 일반적으로 문제를 더이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다
3. 단순한 문제 해결하기
   • 문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결한다
     • 이를 재귀의 기초(base case)라고 한다
     • 재귀의 기초는 재귀의 탈출 조건을 구성한다
4. 복잡한 문제 해결하기
   • 남아있는 복잡한 경우를 해결한다
5. 코드 구현하기