재귀함수 (코플릿)

학습 목표✏️

1. 재귀의 의미를 설명할 수 있다.
2. Javascript에서 재귀 호출할 수 있다.
3. 재귀함수를 언제 쓰는지 설명할 수 있다.
4. 재귀의 기초(base case)와 탈출 조건에 대해 이해
5. 재귀 함수를 base case와 recursive case로 나눠서 작성

재귀함수 란?

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

언제 재귀함수를 사용하나요?🤔

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

재귀 함수로 문제 해결하기

ex) 함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴합니다.

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

• arrSum: [number] => number

2. 문제를 동일한 방식으로 쪼개고 경우의 수를 나누기

• arrSum([ ]) //입력값이 빈 배열인 경우
• arrSum([요소1, 요소2, ... , 요소n]) // 그렇지 않은 경우

3. 단순한 문제 해결하기(base case)

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결!(재귀의 탈출 조건)

• 함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0!
• 즉, arrSum([ ]) === 0 // 입력값이 빈 배열인 경우 해결!

4. 복잡한 문제 해결하기 (recursive case)

• 길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더하기!
• 즉, arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) //그렇지 않은 경우 : 해결!

5. 코드로 구현하기

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }
 // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

일반적인 재귀함수 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}