코드스테이츠-부트캠프 [자료구조/알고리즘]-재귀

김희목·2024년 3월 11일

알고리즘 자료구조 코드스테이츠

코드스테이츠

목록 보기

27/56

재귀의 이해

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

위 정의를 코드로 표현하면 다음과 같이 작성할 수 있습니다.

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

이 함수를 호출하면

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

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

재귀로 문제 해결하기

그러면 어떻게 하면 재귀를 활용해서 문제를 해결할 수 있는지 아래의 문제를 푸는 과정을 따라가 보면서 알아볼까요?

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

물론 재귀 없이 반복문으로 해결하는 방법도 있습니다. 하지만 이번 챕터는 재귀를 배우는 것이 목적이니, 차근차근 따라오며 재귀를 이해해 보세요. 우선 이론적으로 재귀로 문제를 해결하는 단계는 다음과 같습니다.

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

이 단계를 적용해서 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이 빈 배열을 받게 되면서 문제를 더 이상 쪼갤 수 없게 되었죠? 이로써 문제를 가장 작은 단위까지 쪼갰다고 할 수 있게 되었습니다.

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

위에서 문제를 쪼갠 방식을 반복해서 문제를 계속해서 쪼개면 더 이상 쪼갤 수 없는 상태에 도달하게 됩니다.

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

마지막에는 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 함수를 완성해 보면 다음과 같습니다.

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

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

arrSum 함수가 작동하는 방식을 시각적으로 확인해 볼까요?

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

모든 재귀 함수는 반복문(while문 또는 for문)으로 표현할 수 있습니다. 그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.

이 밖에도, 재귀는 알고리즘 문제의 많은 부분을 차지합니다. 앞으로 만나게 될 다양한 과제와 기업의 입사 시험(코딩 테스트, 알고리즘 테스트 등)이나 직무면접에서 활용할 수 있기 때문에, 기초를 확실하게 다져두는 게 바람직합니다.

재귀적으로 사고하기

재귀는 자전거를 타는 것과 비슷합니다.

자전거 타는 법을 처음 배울 때, 다른 사람이 타는 것을 옆에서 지켜보면 꽤 쉬워 보입니다. 그러나 막상 내가 타려고 하면, 생각보다 잘 안 됩니다. 자전거를 잘 타는 방법은 계속 시도하고 연습하는 수밖에 없습니다. 재귀 역시 마찬가지입니다. 자연스러워질 때까지 연습해야 합니다.

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을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([])의 리턴값은 0입니다.

arrSum: [number] => number
arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결!
arrSum([요소1, 요소2, ... , 요소n])

4. 복잡한 문제 해결하기

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

길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더합니다.
arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결!
배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, 함수 arrSum을 재귀적으로 구현할 수 있습니다.

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

예1)
fac(5) = 5 * (4!) === 5 * 24 === 120
fac(4) = 4 * (3!) === 4 * 6 === 24
fac(3) = 3 * (2!) === 3 * 2 === 6
fac(2) = 2 * (1!) === 2 * 1 === 2
fac(1) = 1

// 즉 함수로 만들어 보면
function fac(n) {
	if(n === 1) {
    	return 1;
     }
     return n * fac(n-1);
 }
 
 즉 fac(5)를 입력하면 120이란 값이 나오게 된다.

즉 이 예제에서
base case 즉 재귀의 탈출 조건과 관련이 있는 것은
fac(1) === 1 이란 값이고 if문이 됩니다.

recursive case 즉 문제를 작게 쪼개는 것은
return n * fac(n-1); 이 됩니다.

JSON

JSON의 탄생 배경

JSON은 JavaScript Object Notation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷입니다.

네트워크를 통해, 어떤 객체 내용을 다른 프로그램에 전송한다고 가정하겠습니다.

이 객체 내용을 일종의 메신저 혹은 채팅 프로그램에서 쓰는 하나의 메시지라 한다면, 다음 객체를 어떻게 전송할 수 있을까요?

const message = {
  sender: "김코딩",
  receiver: "박해커",
  message: "해커야 오늘 저녁 같이 먹을래?",
  createdAt: "2021-01-12 10:10:10"
}

메시지 객체가 전송할 수 있게 하려면, (1)메시지를 보내는 발신자와 메시지를 받는 수신자가 같은 프로그램을 사용하거나, (2)문자열처럼 범용적으로 읽을 수 있는 형태여야 합니다.

객체는 타입 변환을 이용해 String으로 변환할 경우 객체 내용을 포함하지 않습니다.

JavaScript에서 객체를 문자열로 변환하기 위해 메서드(message.toString())나 형 변환(String(message))을 시도하면, [object Object]라는 결과를 리턴합니다.

이 문제를 해결하는 방법은 객체를 JSON의 형태로 변환하거나 JSON을 객체의 형태로 변환하는 방법입니다. 이를 위한 메서드는 다음과 같습니다.

JSON.stringify : 객체를 JSON으로 변환합니다.
JSON.parse : JSON을 객체로 변환합니다.

let transferableMessage = JSON.stringify(message)

console.log(transferableMessage) 
// `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`

console.log(typeof(transferableMessage))
// `string`

stringify하는 이 과정을 직렬화(serialize)한다고 합니다.

JSON으로 변환된 객체의 타입은 문자열입니다.

발신자는 객체를 직렬화한 문자열을 누군가에게 객체의 내용을 보낼 수 있습니다. 그렇다면 수신자는 이 문자열 메시지를 어떻게 다시 객체의 형태로 만들 수 있을까요? JSON.stringify와 정반대의 작업을 수행하는 메서드 JSON.parse를 사용할 수 있습니다.

let packet = `{"sender":"김코딩","receiver":"박해커","message":"해커야 오늘 저녁 같이 먹을래?","createdAt":"2021-01-12 10:10:10"}`
let obj = JSON.parse(packet)

console.log(obj)
/*
 * {
 * sender: "김코딩",
 * receiver: "박해커",
 * message: "해커야 오늘 저녁 같이 먹을래?",
 * createdAt: "2021-01-12 10:10:10"
 * }
 */

 console.log(typeof(obj))
 // `object`