TIL44: Recursion

Recursion(재귀)

• 재귀적으로 사고하는 방법
  • 주어진 복잡한 문제를 잘게 쪼개어 작은 문제들로 바꾸어 생각하기
  • 각 작은 문제들의 구조가 비슷할 경우 함수의 재귀적 호출하기
  • 재귀적 구조에서 탈출하는 조건 표현하기
  • 단순한(더 이상 쪼갤 수 없는) 문제들 먼저 해결하기: Base Case
  • 복잡한 문제 해결하기: Recursive Case

Recusive Function(재귀 함수) 활용: 재귀 함수의 호출은 아래와 같은 상황에서 매우 적합합니다.

• 주어진 문제가 구조는 비슷하고 더 작은 문제로 나뉘어 질 수 있는 경우
• 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우
• 특히 자료가 Tree구조일 경우: JSON, DOM

아래는 재귀함수를 호출하여 문제를 해결하는 유사코드 예시입니다.

function arrSum(arr) {
  // 재귀의 기초 (Base Case)
  // 문제를 더 이상 쪼갤 수 없을 경우
  if (arr의 길이가 0인 경우) {
      return 0;
  }
  // Recursive Case
  // 그렇지 않은 경우
  // head: 배열의 첫 요소
  // tail: 배열의 첫 요소만 제거된 배열
  return head + arrSum(tail);
}

재귀의 장/단점
모든 재귀와 관련된 문제는 재귀함수 호출없이 while 또는 for loop으로 표현이 가능합니다. 하지만 재귀를 사용한 코드가 대부분 더욱 간결하고, 일부의 경우에는 이해하기도 쉽습니다.
다만 최종적으로 값이 반환되기 전까지 함수의 매 호출마다 Call Stack을 생성하므로 과도하게 사용될 경우 Memory Leak의 우려가 있습니다.

코드 및 자료 출처: 코드스테이츠(CodeStates)