Chapter [ 재귀 함수 ]

재귀함수란?

1. 함수 내에서 자기 자신(실행 중인 함수)을 다시 호출하는 함수
2. 함수의 복사본을 하나 더 만들어서 복사본을 실행한다.
3. 함수 안에 함수가 함수를 부르고 그 함수가 또 함수를 부르기를 반복하기 때문에 결과는 무한히 반복한다. ( return문 꼭 필요! )

1. 재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

2. 재귀적 사고 연습하기

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

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

   • 중요한 관점은 입력값이나 문제의 순서와 크기

3. 단순한 문제 해결하기

   • 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부른다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

4. 복잡한 문제 해결하기

5. 코드 구현하기

function arrSum(arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  /*
  * Recursive Case : 그렇지 않은 경우
  * 문제를 더 이상 쪼갤 수 없는 경우
  * head: 배열의 첫 요소
  * tail: 배열의 첫 요소만 제거된 배열
  */
  return 더 작은 문제로 새롭게 정의된 문제;
}

3. factorial로 알아보는 재귀

function fac(n) {
   if(n ===1) {
    return 1;
   }
    return n * fac(n-1) 
}

• 그림으로 알아보기