재귀?

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

재귀의 사전적 정의는 원래의 자리로 되돌아오는 것을 의미하며, 위의 이미지처럼 원래의 상태로 계속해서 되돌아오는 것으로 해석할 수 있다. 코드로 작성하면 아래처럼 표현할 수 있다.

function recursion () {
	console.log("This is");
	console.log("recursion!");
	recursion(); // 자기 스스로를 호출함
}

함수를 호출하게 되면 자기 자신을 끝없이 호출하며 같은 코드가 계속해서 실행된다.

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

재귀로 문제 해결하기

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

위의 문제를 간단히 해결하는 방법은 반복문을 이용하는 것이겠지만, 재귀 함수를 배우기 위해 한 단계씩 과정을 이해해보자. 이론적으로 재귀로 문제를 해결하는 과정은 다음과 같다.

문제를 좀 더 작게 쪼갠다.

1번을 반복하여, 문제가 더는 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갠다.

가장 작은 단위의 문제를 풀어서 전체 문제를 해결한다.

1. 문제를 작게 쪼개기

단순하게 생각했을 때 [1, 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])
...

2. 반복하여 문제를 가장 작은 단위로 쪼개기

위의 방법으로 계속 문제를 쪼개면 빈 배열을 받게 되면서 가장 작은 단위로 쪼개게 된다.

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

3. 문제 해결하기

이제 가장 작은 단위의 문제를 해결할 차례이다. 쪼갤 때 같은 방식을 반복하여 쪼갰기 때문에 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있게 된다. 2번에서 도달한 가장 작은 문제는 arrSum([])이었다. 빈 배열의 합은 0이므로 0을 리턴해주면 되고, 이렇게 가장 작은 문제를 해결하게 되면 쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 된다.

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 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고 최종적으로는 문제 전체가 해결된다. 위 단계를 반영해 arrSum 함수를 작성하면 다음과 같다.

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

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

arrSum 함수가 내부에서 arrSum 함수를 호출하면서 문제가 쪼개어져 나가고 결국 문제를 쪼갤 수 없는 arrSum([])까지 함수가 호출되는 것을 볼 수 있다. arrSum([])는 조건문에 의해 호출을 멈추고 0을 리턴한다. 그 결과 중첩되었던 함수들도 연쇄적으로 숫자를 리턴하고 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.

재귀는 언제 사용할까?

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

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

중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

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);
                           }
                        }
                    }
                }
            }
        }
    }
 }

모든 재귀 함수는 반복문으로 표현할 수 있다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다. 이 밖에도 재귀는 알고리즘 문제의 많은 부분을 차지하기 때문에, 앞으로 만날 다양한 과제와 기업의 코딩/알고리즘 테스트, 직무면접에서 활용할 수 있기 때문에 기초를 확실하게 다져두는게 바람직하다.

재귀의 활용

재귀적으로 사고하기

재귀는 정의와 사용법을 배울 때는 그럭저럭 이해가 가는 것 처럼 느껴지지만, 막상 활용을 하려면 적용하기 쉽지 않다. 이를 위해 재귀적으로 사고하는 방법에 대한 가이드를 배운다.

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

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

함수 arrSum의 경우 number타입을 요소로 갖는 배열을 입력받고 number타입을 리턴한다.
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을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때의 리턴값은 0이다.
arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우면, 0을 리턴
arrSum([요소1, 요소2, ... , 요소n])

4. 복잡한 문제 해결하기

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

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 더 작은 문제로 새롭게 정의된 문제
}

Uploaded by N2T

티스토리툴바

재귀

재귀?