[JS] 재귀

* 자기 자신을 호출하는 함수인 재귀(recursion) 함수를 활용하는 방법

재귀의 개념

재귀 : 원래의 자리로 되돌아가거나 되돌아옴.

표준국어대사전에서는 위와 같이 재귀의 뜻을 정의하고 있다.
재귀의 시각적 예시를 든다면 계속해서 원래의 상태로 돌아오는 아래 이미지와 같을 것이다.

위 정의와 예시를 참고하여 재귀를 코드로 표현하면 다음과 같이 작성할 수 있다.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

recursion 함수를 호출하면 자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다.

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

재귀로 문제 해결하기

문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 `arrSum` 을 작성하시오.

어떻게 하면 재귀를 활용해서 문제를 해결할 수 있는지 위의 문제를 푸는 과정을 따라가 보면서 알아보자.
이론적으로 재귀로 문제를 해결하는 단계는 다음과 같다. (물론 재귀 없이 반복문으로 해결하는 방법도 있다. )

1. 문제를 좀 더 작게 쪼갠다.
2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

이 단계를 적용해서 arrSum 함수를 작성해 보자.

🟣 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정

1. 문제를 작게 쪼개기

어떻게 하면 arrSum 함수로 [1, 2, 3, 4, 5] 의 합을 구하는 과정을 더 작게 쪼갤 수 있을까?

단순하게 생각해 보면, 배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다 [2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제이고, 여기서 또 [2, 3, 4, 5]의 합을 구하는 것보다 [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([1, 2, 3, 4, 5]) === arrSum([1, 2, 3, 4]) + 5
arrSum([1, 2, 3, 4]) === arrSum([1, 2, 3]) + 4
...

2. 문제를 가장 작은 단위로 쪼개기

위에서 문제를 쪼갠 방식을 반복해서 문제를 계속해서 쪼개면 더 이상 쪼갤 수 없는 상태에 도달하게 된다.
마지막에는 arrSum 이 빈 배열을 받게 되면서 문제를 더 이상 쪼갤 수 없다.
이로써 문제를 가장 작은 단위까지 쪼갰다고 할 수 있게 되었다.

...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])

// 또는 뒤에서부터
arrSum([1, 2, 3]) === arrSum([1, 2]) + 3
arrSum([1, 2]) === arrSum([1]) + 2
arrSum([1]) === arrSum([]) + 1

3. 문제 해결하기

문제가 더 쪼개지지 않게 되면, 가장 작은 단위의 문제를 해결한다.
문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있게 된다.
- 2번에서 도달한 가장 작은 문제는 arrSum([]) 이었다.
- 빈 배열의 합은 0이므로, 0을 리턴해준다.
- 이렇게 가장 작은 문제를 해결하는 순간, 아래 코드처럼 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 된다.
- arrSum 함수의 리턴 값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결되는 것을 볼 수 있다.

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

// 가장 작은 경우의 해결책을 적용한다.
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;


// 또는 뒤에서부터
arrSum([1]) === arrSum([]) + 1 === 1 + 0 === 1;
arrSum([1, 2]) === arrSum([1]) + 2 === 1 + 2 === 3;
arrSum([1, 2, 3]) === arrSum([1, 2]) + 3 === 3 + 3 === 6;
arrSum([1, 2, 3, 4]) === arrSum([1, 2, 3]) + 4 === 6 + 4 === 10;
arrSum([1, 2, 3, 4, 5]) === arrSum([1, 2, 3, 4]) + 5 === 10 + 5 === 15;

위 단계를 반영해서 arrSum 함수를 완성해 보면 다음과 같다.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

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

arrSum 함수가 작동하는 방식 디버깅

arrSum 함수 작동 방식 시각적으로 확인

* 재귀로 문제가 쪼개어지는 과정
: arrSum 함수가 내부에서 arrSum 함수를 호출하면서 문제가 쪼개어져 나가고, 결국 문제를 더 이상 쪼갤 수 없는 arrSum([]) 까지 함수가 호출된다.

* 재귀로 문제가 해결되는 과정
: arrSum([]) 는 조건문에 의해 더 이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다.
그 결과 중첩되어 있던 함수들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.

재귀는 언제 사용하는 게 좋을까?

재귀는 다음과 같은 상황에서 매우 적합하다.

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

모든 재귀 함수는 반복문(while 문 또는 for 문)으로 표현할 수 있다.

그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.
이 밖에도, 재귀는 알고리즘 문제의 많은 부분을 차지한다.

// 반복문 사용

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }
 
 // 재귀함수 사용 (대략 이런 식)
 
 function recursiveFunc(n, arr, depth) {
    if (depth === arr.length) {
        someFunc(...arr);
        return;
    }
    for (let i = 0; i < n; i++) {
        arr[depth] = i;
        recursiveFunc(n, arr, depth + 1);
    }
}

recursiveFunc(n, [], 0);

Guide : 재귀적으로 사고하기

위에서의 arrSum 함수를 이용해 재귀적으로 사고하는 과정을 알아보겠다.

1. 재귀 함수의 입력값과 출력값 정의하기

재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것이다.
함수의 입출력 값을 정의하는 것은 그 첫 출발점이며, 재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 된다.

함수 arrSum 의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴한다.
이를 좀 더 간단하게 표기하면 다음과 같다.
arrSum: [number] => number ← 입출력 값 정의

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

다음으로는 주어진 문제를 어떻게 쪼갤 것인지 고민한다.
문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.
- 일반적으로, 입력값을 이 기준으로 정한다.
- 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다.
주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.
** 그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면, 문제를 제대로 구분한 것이다.

함수 arrSum 의 경우 입력값인 배열의 크기에 따라, 더 작은 문제로 나눌 수 있다.
arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다.
- 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈다.
- 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다.
- 각각의 경우는 다른 방식으로 처리해야 한다.
- arrSum([ ]) ← 입력값이 빈 배열인 경우
- arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다.
- 이를 재귀의 기초(base case)라고 부른다.
- 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다.
그렇다고 문제를 덜 쪼갠 상태에서 탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 된다.
-> 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요하다.

함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0이다.
- arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결! 탈출가능!!!
- arrSum([요소1, 요소2, ... , 요소n])

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결한다.

길이가 1 이상인 배열이 함수 arrSum에 입력된 경우,
입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더한다.
- arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
- 3번에서의 base case에서 쪼개진 히스토리를 따라서 쭉쭉 올라가면 된다.
- 즉, 배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum 을 재귀적으로 구현할 수 있다.
  - 첫 요소는 arr.shift로 떼어내주고(리턴값이 떼어낸 요소) /
  - 작은 문제는 첫 요소가 떨어져나간 나머지 배열들이다.

5. 코드 구현하기

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

  // recursive case : 그렇지 않은 경우
  return 요소1 + arrSum([요소2, ... , 요소n]);
}

📌 재귀 함수의 템플릿

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

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

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

factorial 문제 풀어보기

문제

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 `fac` 을 작성하시오.
  예1) fac(5)  ===  5 * 4 * 3 * 2 * 1  ===  120
  예2) fac(3)  ===  3 * 2 * 1  ===  6

base case와 recursive case 찾기

recursive case :
fac(5) === 5 * fac(4)
fac(4) === 4 * fac(3)
...
fac(2) === 2 * fac(1)
fac(1) === 1
base case: fac(1) === 1 또는 fac(0) === 1 -> 탈출

풀리는 과정

풀리는 과정 (아래에서부터) :
fac(5) === 5 * fac(4) === 120
^
fac(4) === 4 * fac(3) === 24
  ^
fac(3) === 3 * fac(2) === 6
  ^
fac(2) === 2 * fac(1) === 2
      ^
fac(1) === 1 (여기서부터 시작)

함수로 표현

function fac(n) {
  if (n ===1) { return 1 }
  return n * fac(n-1)
}

시각적으로 확인

728x90

저작자표시

'FE > JavaScript' 카테고리의 다른 글

[JS] JSON.stringify 재귀를 이용하여 직접 구현하기 (0)	2023.04.12
[JS] JSON 개요 (JavaScript Object Notation) (0)	2023.04.12
[JS] fetch를 이용한 네트워크 요청 - 2/2 (활용) (0)	2023.03.27
[JS] Node.js 내장 모듈인 fs 모듈로 비동기 실습 - 2/2 (활용) (0)	2023.03.26
[JS] 비동기 흐름 : 배열 메서드 구현해보기 (Underbar) - 중 (0)	2023.03.25

개발해도유