재귀(Recursion)

어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

따라서, 재귀 함수는 함수 자기 자신을 계속 호출하는 함수를 뜻한다.

재귀 함수의 두 가지 조건을 다음과 같다.

• 종료 조건
• 재귀적인 호출

재귀 함수의 예시

아래 예시는 음수가 아닌 정수를 입력 받았을 때, 팩토리얼을 재귀 함수로 구현한 예시이다.

function factorial(num) {
  if ( num <= 0 ) return 1;	// 종료 조건

  return num * factorial(--num); // 재귀적인 호출
}

재귀 함수가 될 수 없는 것

아래 조건들을 지키지 않으면 콜스택은 오버플로우되고 에러가 발생한다.

• 종료 조건이 없는 것
• 재귀 호출에 올바른 인수를 전달하지 않는 것(올바른 반환값이 아니게 됨)
• 반환값이 없는 것

헬퍼 메소드 재귀

재귀에 헬퍼 함수를 구현해보자.

기본적인 틀은 아래와 같다.

function outer(input) {
  
  let outerScopedVariable = [];
  
  function helper(helperInput) {
    // modify the outerScopedVariable
    helper(helperInput--)
  }
  
  helper(input)
  
  return outerScopedVariable;
}

헬퍼 함수는 아래의 두 가지 구성요소로 이루어진다.

• outer 함수
• inner 함수 (재귀 함수)

배열에서 모든 홀수값을 수집하는 간단한 예시를 헬퍼 함수로 구현해보자.

function collectOddValues(arr) {
  let result = [];
  
  function helper(helperInput) {
    if(helperInput.length === 0) {
      return;
    }
    
    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }
    
    helper(helperInput.slice(1));
  }
  
  helper(arr);
  
  return result;
}

헬퍼 함수가 아닌 순수 재귀

배열에서 모든 홀수값을 수집하는 예시를 헬퍼 함수가 아닌 순수한 재귀 함수로 구현해보자.

function collectOddValues(arr) {
  let newArr = [];
  
  if(arr.length === 0) {
    return newArr;
  }
  
  if(arr[0] % 2 !== 0) {
    newArr.push(arr[0]);
  }
  
  newArr = newArr.concat(collectOddValues(arr.slice(1)));
  
  return newArr;
}

순수 재귀 팁

• 배열을 사용하고 헬퍼 함수 없이 순수 재귀함수를 작성하는 경우에 배열을 복사하는 slice, spread 연산자, concat 같은 메서드를 사용할 수 있다. 그러면 배열을 변경할 필요가 없다.
• 문자열은 변경할 수 없다. 다라서 slice, substr, substring 등의 메서드를 사용해야 한다.
• 객체의 경우에는 Object.assign이나 spread 연산자를 사용하는 게 유용하다.