🔍 재귀

자기 자신을 호출하는 함수를 재귀함수라고 하며, 재귀함수를 활용해 반복적인 작업을 해야하는 문제를 더욱 간결한 코드로 풀어낼 수 있다.

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우, 혹은 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우에 사용한다. 따라서, 모든 재귀함수는 반복문으로 표현할 수 있다.

재귀로 문제를 해결하는 방법은 아래와 같다.

1. 문제를 작게 쪼갠다.
2. 1번과 같은 방식으로, 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

위의 방법을 이용해 arrSum 함수로 [1, 2, 3, 4, 5] 의 합을 구하는 과정을 예시로 들면, 아래와 같다.

// 문제를 가장 작은 단위로 쪼갠다.
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([]) // 가장 작은 문제 = arrSum([])

위 단계를 반영해, 함수를 완성해보면 아래와 같다.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  
  // 조건문에 의해 더 이상 자기자신을 호출하지 않고, 숫자 0를 return하면서 종료. 
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr) // 0번째 인덱스를 삭제해가면서 ++
}

👀 재귀적으로 사고하기

1) 재귀 함수의 입력값과 출력값을 정의한다.

이때, 추상적으로 또는 단순하게 정의해야 한다.

• arrSum: [number] => number ← 입출력값 정의
  
  

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

문제를 쪼갤 기준을 정하고, 기준에 따라 더 큰 경우와 작은 경우로 구분할 수 있는 지 확인한다. 일반적으로, 입력값을 기준으로 정한다.

이때, 중요한 관점은 입력값, 문제의 순서, 크기로, 문제를 구분하는 데 수월하다.

• 함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다.

• arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하다.

• 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있으며, 각각 다른 방식으로 처리해야 한다.
  arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3) 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결하며 이를 재귀의 기초(base case)라고 한다.
재귀의 기초는 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.
따라서, 문제를 최대한 작게 쪼갠 후에 해결하는 것이 중요하다.

• arrSum: [number] => number
arrSum([ ]) ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

4) 복잡한 문제 해결하기

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

아래는 일반적인 재귀 함수의 템플릿이다.

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

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

아래는 위의 템플릿을 적용해 팩토리얼을 구현한 예제이다.

function factorial(n){

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

Reference: 코드스테이츠