재귀 함수란?

어떤 함수가 스스로를 호출하는 함수로, 반복적인 수행을 할때 더 간결하게 표현하기 위해 재귀적 사고를 바탕으로 문제를 해결한다.

• 어떤 부분을 반복 시킬지
• 어디서 반복을 종료시킬지 (종료시키는 조건)

이 두가지를 재귀 알고리즘을 생각할 때 주의 깊게 생각해야 할 조건으로 삼고 재귀 함수를 만들때 주의하여 만든다.

재귀함수를 사용하는 경우

1) 해결하려는 문제를 비슷한 구조의 더 작은 단위 문제로 쪼갤 수 있을 때

2) 중첩된 반복문이 많아 그 반복 횟수를 파악하기 어려울 때

[예제] 배열을 입력받아, 배열의 요소들의 합을 리턴하는 함수를 구할 때,

• 재귀함수 없이 반복문을 사용

  const arrSum(arr){
    let result = 0;
    for(let i=0;i<arr.length;i++){
      result += arr[i];
    }
    return result;
  }

• 재귀함수로 반복 과정 처리

const arrSum(arr){
//base case
  if(arr.length === 0){
    return 0;
  }
  else{
  //recursive case
    return arr[0] + arrSum(arr.slice(1));
  }
}

재귀함수를 사용할때 고려해야할 조건

1. 반복되는 부분 찾기
2. 반복되는 재귀함수를 종료시킬 시점이 언제인지(재귀의 기초 - base case: 더이상 문제를 쪼갤 수 없는 경우)

위의 arrSum 함수를 재귀함수로 작성할 때, arr로 [1,2,3,4]를 입력받는다고 하자.

arrSum([1,2,3,4])

1 + arrSum([2,3,4])

2 + arrSum([3,4])

3 + arrSum([4])

4 + arrSum([])

배열의 요소를 하나씩 잘라나가는 방식으로 문제를 해결한다. 더 작은 단위로 문제를 쪼개는 게 재귀함수의 포인트이다.

요소 한개를 선택하고 나머지는 arr.slice(1) 로 잘라내어 잘라낸 배열을 다시 재귀함수로 넣는다.
더이상 잘라낼 요소가 없을 때, arrSum([])과 같이 빈 배열이 나와 더이상 더할 값이 없는 경우까지 나오게 된다.

이때를 종료해야할 시점으로 분류하여 종료해야할 시점을 만났을 때(base case),
if(arr.length === 0) 조건문을 걸어 마지막 재귀에 도달했을 때 return 0을 돌려주어 0+4+3+2+1 순으로 값을 더해나가 결과값을 돌려준다.

위와 같은 사고과정을 수도코드로 작성해본다면, 재귀함수 탬플릿으로 반복하는 문제에 대해서 재귀적으로 풀어나갈 때 참고해볼 수 있다.

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}