재귀(recursion)

어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법

함수가 자기 자신을 다시 호출하는 것을 재귀 호출 방식 이라고 한다.

---

재귀는 언제 사용할까?

1. 주어진 문제가 (구조가 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우
2. 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우

---

재귀적으로 생각하기

재귀적으로 사고하려면 문제를 바라보는 시각을 바꿔야 한다.

1. 재귀 함수의 입력값과 출력값 정의하기

   • 문제 상황을 해석하기 위해 정의한다.

2. 문제를 쪼개고 경우의 수를 나누기

   • 문제를 쪼개기 위해선 먼저 문제를 기준에 따라 큰 경우와 작은 경우로 구분할 수 있어야 한다.
   • 구분 기준은 순서와 크기
   • 구분된 문제들을 푸는 방식이 같다면 문제를 제대로 구분한 것

   arrSum([1, 2, 3, 4]) 
   arrSum([1, 2, 3])

   • 구분을 했다면 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.

   arrSum([])
   arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기 (base case)

   • 이 부분은 재귀의 기초라고 부른다.
   • 이후 재귀의 탈출 조건을 구성한다.

4. 복잡한 문제 해결하기

   • 큰 경우와 작은 경우로 나눴다면 이를 일반화, 추상화를 시킨다.

   arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ... , en])

5. 코드 구현하기