재귀

재귀함수는 자기 자신을 호출하는 함수로, 재귀를 사용하기 적합한 경우는 아래와 같다.

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우
• 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

재귀 함수는 자기 자신을 호출하는 것을 통해 반복적인 작업을 간결한 코드로 구현할 수 있다는 장점이 있었다. 모든 재귀 함수는 반복문으로 표현할 수 있다. 하지만 중첩반복문을 수십개씩 사용해아하는 경우, 탈출 기준을 세우고 그 기준에 이르기까지 반복적으로 자기 자신(함수)를 호출해 실행시키는 것이 훨씬 더 코드가 깔끔하고 이해하기도 쉬울 것이다.

비슷한 구조의 더 작은 문제로 쪼개고, 더는 같은 방식으로 나뉘어지지 않는 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결하는 것이 재귀를 활용해 문제를 해결하는 방법이다. 이론적인 건 알겠고, 왜 사용하는지도 알겠는데 막상 문제를 푸는 건 다른 문제인 것 같다... 그래도 리액트와 서버에 치이다 오랜만에 코플릿 문제를 푸는 과제를 진행해서 꽤 재밌게 느껴졌다ㅎㅎㅎ 알고리즘 문제에서 특히 중요하다고 하니 문제들을 직접 풀어보면서 유형을 익히는 것이 중요할 것 같다.

---

일반적인 재귀 함수의 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

템플릿을 활용한 예시 (factorial)

function factorial(num) {
  if(num <= 1) return 1;
  return num * factorial(num-1);
}


// 결과 도출 과정

factorial(5)

function factorial(5) {
  if(5 <= 1) return 1;
  return 5 * factorial(4); // factorial(4) 재귀 호출
}

function factorial(4) {
  if(4 <= 1) return 1;
  return 4 * factorial(3); // factorial(3) 재귀 호출
}

function factorial(3) {
  if(3 <= 1) return 1;
  return 3 * factorial(2); // factorial(2) 재귀 호출
}

function factorial(2) {
  if(2 <= 1) return 1;
  return 2 * factorial(1); // factorial(2) 재귀 호출
}

function factorial(1) {
  if(1 <= 1) return 1; // if문 true, factorial(1) => return 1;
  return 1 * factorial(0);
}

// 더이상 쪼갤 수 없는 조건으로 설정한 base case 값을 return
// 재귀함수 호출을 멈추고, 콜스택에 쌓여있던 함수 호출 결과를 return 시작

function factorial(2) {
  if(2 <= 1) return 1;
  return 2 * 1; // factorial(2) => return 2 * 1;
}

function factorial(3) {
  if(3 <= 1) return 1;
  return 3 * 2 * 1; // factorial(3) => return 3 * 2 * 1;
}

function factorial(4) {
  if(4 <= 1) return 1;
  return 4 * 3 * 2 * 1; // factorial(4) => return 4 * 3 * 2 * 1;
}

function factorial(5) {
  if(5 <= 1) return 1;
  return 5 * 4 * 3 * 2 * 1; // factorial(5) => return 5 * 4 * 3 * 2 * 1;
}

// 결과
factorial(5) // 120