JavaScript _tip / 재귀적으로 생각하기

코딩테스트 문제 80% 이상 차지하는 재귀함수 어떻게 해결해야 될까요 ?

재귀함수 정말 난해하고 어려운 내용 중 하나라고 생각합니다. 뿐만아니라 재귀적으로 해결 하기 위해서는

문제를 쪼개고 나누는 연습을 습관처럼 해야 논리적 사고가 함양되고 재귀문제를 수월하게 해결 할 수 있습니다. 그래서 오늘은 재귀적으로 생각하기에 대해 블로깅을 하겠습니다! 

 

---

# 재귀의 이해

재귀는 어떤 문제를 해결 할 때, 구조는 동일 하지만 더 작은 경우를 해결함으로써 그문제를 해결 하는 방법을 재귀 라고 합니다.

 

재귀는 주어진 문제가(구조가 비슷) 더 작은 문제로 나뉘어 질 수 있는 경우와 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우에 사용하기 매우 적합합니다.

 

---

# 재귀적으로 사고하기

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

재귀함수를 통해 어떤 문제를 풀때 문제를 가장 추상적으로 또는 가장 단순하게 정리를 합니다.

 

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

재일 중요한 단계입니다. 주어진 문제를 어떻게 쪼개고 어떤 기준으로 문제를 해결할지 고민해야 됩니다!

보편적으로는 입력값(매개변수)이 기준을 정하는 대상입니다. 여기서 가장 중요한 포인트는 순서와 크기 입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다. 그리고 구분된 문제들을 푸는 방식이 같다면, 문제를 제대로 구분한 것입니다.

 

3. 단순한 문제 해결하기

문제를 여러 경우로 구분 한뒤 쉬운 문제부터 해결합니다. 즉 문제를 더 이상 쪼갤 수 없고 재귀 함수 구현시 탈출 조건을 만듭니다. 이를 재귀의 기초(base case)라고 부릅니다.

 

4. 복잡한 문제 해결하고 코드구현하기

남아있는 복잡한 경우를 순서와 크기를 기준으로 구분하여 문제를 해결하고 코드로 구현하면 됩니다.

 

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

 

---

# 일반적인 재귀 함수의 탬플릿

function 재귀함수(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // ex1. someValue + recursive(input1Changed, input2Changed, ...)
  // ex2. someValue * recursive(input1Changed, input2Changed, ...)
}

 

보편적으로 많이 사용하는 재귀 함수 탬플릿입니다! 재귀적 사고 연습에 많이 유용합니다. 

재귀함수 연습에 많이 활용해서 재귀적 사고력을 길러봅시다!