JS - 재귀함수

재귀함수

재귀란 어떠한 문제를 동일한 구조의 더 작은 문제로 나누고, 이 작은 문제로 전체 문제를 해결하는 방법을 재귀(recursion)이라고 한다. 재귀를 사용하면 코드가 더 간결하고 이해하기 쉽게 바뀐다.

재귀를 사용하기 좋은 경우는

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

중첩된 반복문이 많은 경우

재귀적 사고

어떠한 문제를 재귀를 통해 해결하려 할 때, 가장 먼저 단순하고 추상적이게 정의해야 한다. 예를 들어, 함수 arrSum라는 함수가 있다 하면 이 함수는 number 타입을 요소로 갖는 배열을 입력 받고, number타입을 리턴 한다고 해보자

arrSum: [number] => number

다음은 주어진 문제를 어떻게 쪼갤 것인지 생각해야 한다. 주어진 기준에 따라 더 작은 경우와 더 큰 경우를 생각해본다. 이 때 입력값이나 문제의 순서와 크기를 잘 생각해야 한다. 이제 문제를 더이상 쪼갤수 있는 경우와 없는 경우를 나눠보자.
함수 arrSum은 입력값이 빈 배열과 그렇지 않은 경우로 나눌 수 있다.

arrSum: [number] => number
arrSum([ ])
arrSum([1, 2, 3, ... , n])

문제를 여러 경우로 나눈 다음에, 가장 해결하기 쉬운 문제부터 해결한다. 여기서는 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열인 경우이고, 이 때 리턴값은 0이다.

arrSum: [number] => number
arrSum([ ]) = 0
arrSum([1, 2, 3, ... , n])

다음으로 복잡한 문제를 해결한다.

길이가 1이상인 배열이 함수 arrSum에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(head), 나머지 요소를새로운 입력값으로 갖는 문제로 구분한다. 이에 대한 결과를 head에 더한다.

배열의 head와 나머지부분(tail)만 안다면 재귀로 표현할 수 있다.

function arrSum(arr) {
  // 문제를 더 이상 쪼갤 수 없는 경우
  if ( arrSum.length === 0 ) {
    return 0;
  }
  
  // 그렇지 않은 경우
  // head 배열의 첫 요소
  // tail 배열의 첫 요소만 제거된 부분, 나머지 부분
  return head + arrSum(tail);
}

즉, 재귀의 기본틀을 이렇게 표현할 수 있다.

function recursive(el1, el2, ...) {
  // 문제를 더 이상 쪼갤 수 없는 경우
  if ( 문제를 더 이상 쪼갤 수 없는 경우 ) {
    return 단순한 문제의 해답;
  }
  
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제;
  // ex) return someValue + recursive(....)
}

예제

문제 - 배열을 입력받아 모든 요소의 합을 리턴해야 한다.

입력

인자(arr) - number : 타입을 요소르 갖는 배열

출력

number 타입을 리턴해야 한다

arr[0] + arr[1] + arr[2] + ... + arr[n-1]

arr.length는 n

주의사항

함수 arrSum은 재귀의 형태로 작성해야 한다

반복은(for문 while문)은 사용하지 않는다

입력받은 배열은 호출 뒤에도 처음 상태를 유지해야 한다

입력으로 들어오는 모든 요소는 정수로 간주한다

빈 배열의 합은 0이다

입출력 예시

let output = arrSum([-1, -2, 1, 3);
console.log(output); // -> 1

풀이

function arrSum(arr) {
  if ( arr.length === 0 ) {
    return 0;
  }
  
  const head = arr[0];
  const tail = arr.slice(1);
  return head + arrSum(tail);
}