[CS] 재귀(recursion) Day-24

재귀란?

함수가 스스로를 호출하는 것을 말합니다.

문제가 있고, 문제를 더 작은 문제로 나눌 수 있다. 더 작은 문제를 해결하여 전체 문제를 해결하는 방법을 재귀(recursion)이라고 한다.

재귀(recursion)을 사용하면 코드를 간결하게 만들고, 이해하기 쉽습니다.

재귀를 잘하기 위해서는 문제를 쪼개 생각하는 습관을 길러야 합니다.

재귀를 사용하면 좋을 때

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있을 때
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

모든 재귀 함수는 반복문(while 또는 for)로 표현할 수 있습니다. 하지만 재귀를 적용할 수 있는 경우는 더욱 간결하고, 이해하기 쉽습니다.

재귀를 잘 하는 방법

• 재귀 함수의 입력값과 출력값 정의하기
  재귀 함수를 통해 풀고자 하는 문제의 입력값과 출력값을 미리 생각하는 것이 좋습니다.

arrSum: [number] => number

• 문제를 쪼개 경우의 수를 나누기
  문제를 쪼갤 기준을 정하고, 기준에 따라 문제를 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다.

• 단순한 문제 해결하기
  문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초라고 부릅니다. 재귀 함수를 구현할 때 재귀의 탈출 조건을 구성합니다.

• 복잡한 문제 해결하기
  남아 있는 복잡한 경우의 수를 해결합니다.