[TIL] 재귀함수란?

lmimoh·2022년 10월 20일

JavaScript TIL 재귀함수

TIL

목록 보기

16/26

재귀(recursion)함수란?

재귀(recursion) 함수는 자기 자신을 호출하는 함수를 의미한다.

재귀 함수를 사용하는 시기는 다음과 같다.

주어진 문제를 비슷한 구조의 작은 문제 로 나눌 수 있는 경우
반복문이 과하게 중첩되거나 중첩 횟수(number of loops)를 예측하기 어려운 경우

즉, 모든 재귀 함수는 반복문으로 표현할 수 있다. 하지만, 재귀 함수가 적용되는 대부분의 경우에서 재귀를 적용한 코드가 반복문을 사용한 코드보다 간결하다.

재귀(rescursion)로 문제를 해결하는 방식

재귀의 기초(base case) : 문제를 가장 작게 쪼갠 형태를 의미한다.

recursive case : base case에 수렴하기 전 재귀 과정에서 동일하게 적용될 방식 을 의미한다.

즉, 재귀(rescursion)가 사용가능한 문제는 recursive case를 반복 적용했을 때 base case에 수렴한다.

구체적인 제귀적 사고?

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

추상적인 문제를 가장 단순하게 표현하고, 도달하고자 하는 목표를 정의한다.
ex) 전달인자로 배열을 받아 그 합을 구하는 메소드의 경우
arrSum: [number] => number

문제를 쪼개고 경우의 수를 나눈다.

입력값을 기준으로 문제를 작게 쪼갠다.
이때, 구분된 문제를 푸는 방식이 모두 동일하다면 제대로 구분된 것 이다.

arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간(base case)

// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5;
arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9;
arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12;
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14;
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15;

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

가장 작은 문제를 재귀의 기초(base case)라고 부르며 이는 재귀 함수의 탈출 조건 을 구성하게 된다.
탈출 조건이 없는 경우, 재귀 함수는 끝없이 자신을 호출하게 된다.

즉, 문제를 가장 작은 단위까지 쪼개지 못한다면 base case를 설정할 수 없고, 문제를 제대로 해결할 수 없게 된다.

복잡한 문제 해결하기

base case를 제외한 재귀 함수에 반복 적용될 방식(recursive case) 을 해결한다.

function arrSum(arr) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr의 길이가 0인 경우) {
    return 0;
  }

  // recursive case : 그렇지 않은 경우
  return arr.shift() + arrSum(arr);
}

재귀함수의 예시

// 문자열이 담긴 배열을 입력 받아 모든 요소를 합친 문자열을 반환하는 함수

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

// 해당 함수는 빈 배열이라는 base case로 수렴하게 되고
// 매 함수 실행마다 전달인자 arr의 0번째 원소를 합치게 된다.

// input: ['a', 'b', 'c', 'd']
// expected output :
// arrSum(arr) === 'a'.concat(arrSum(['b', 'c', 'd']);
// arrSum(arr) === 'ab'.concat(arrSum(['c', 'd']);
// arrSum(arr) === 'abc'.concat(arrSum(['d']);
// arrSum(arr) === 'abcd'.concat(arrSum([]);
// : 'abcd'