Unit 1 - [자료구조 / 알고리즘 ] 재귀

2023-06-09(금)

 

학습 전

- 자바스크립트 기초 문법 활용할 수 있어야 합니다.

- 조건문, 반복문을 숙지하고 있어야 합니다.

 

 

Chapter 1 . 재귀의 이해

- 재귀란 무엇일까요?

바로 원래 있던 곳으로 다시 돌아온다는 의미를 가지고 있습니다.

우리 컴퓨터 프로그래밍 측면에서 보면 자기 자신을 호출하는 것이라고 볼 수 있습니다.

 

재귀 함수는 그렇다면 자기 자신을 호출하는 함수를 뜻하는 것입니다.

그런데 왜 재귀가 무엇인지, 알았다면 어떻게 사용해야 하는 것인지, 언제 사용하면 좋은지를 알아봅시다.

 

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

이런 코드가 있습니다. 해당 코드를 실행해보면 어떤 결과가 나올까요?

바로 반복적으로 콘솔들을 출력할 것입니다. 이렇게 위의 recursion 함수처럼 자기 자신을 호출하고 끊임없이 반복하는

함수를 재귀 함수라고 합니다. 

 

재귀 함수를 활용하면 반복적인 작업을 수행할때, 좀 더 간결한 코드로 풀어낼 수 있습니다.

 

그렇다면 어떻게 재귀를 활용하여 문제를 해결할까요? 아래 문제를 통해 한번 같이 알아봅시다.

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

이러한 문제가 있으면 어떤식으로 해결하는게 좋을까요? 물론 반복문을 사용하여 해결할 수 있습니다.

하지만 우리는 재귀함수를 배우러 왔으니 한 번 재귀함수를 통해 해결해 봅시다.

 

이론적으로 재귀로 문제를 해결하는 방식은 아래와 같습니다.

1. 문제를 좀 더 작게 쪼갠다.

2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지, 가장 작은 단위로 문제를 쪼갠다.

3. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결한다.

 

이 방식을 통해 우선 배열 [ 1, 2, 3, 4, 5 ] 의 합을 구하는 과정을 재귀로 풀어봅시다.

 

이 배열을 구하는 과정에서 어떻게하면 작게 쪼갤 수 있을까요?

합이라면 1부터 5까지의 값들을 모두 더한 값이 될 것입니다. 그렇다면 우리는 이런식으로 작성해 보겠습니다.

 

[1,2,3,4,5]의 합을 구하는 것 보다, [2,3,4,5] 의 합을 구하는게 더 쉽지 않을까요?

그렇다면 [2,3,4,5]의 합보다 [ 3, 4, 5 ] 가 더 쉬울겁니다. 계속 쪼개볼까요?

[ 4, 5 ]  ,[ 5 ],  [ ] 점점 수를 쪼개가며 결국 빈배열이 될때까지 쪼갤 수 있겠네요.

 

그렇다면 여기서 가장 작은 단위는 []빈 배열을 제외하면 [ 5 ] 가 될 것입니다.

배열 [ 5 ] 는 더할 값이 없으니 그대로 5가 도출 될 것입니다. 그렇다면 [ 4 , 5 ] 는 어떨까요? 이미 5의 값은 더했으니

4와 5를더해준다면 9가 도출 될 것이죠. 이런식으로 점점 문제를 거꾸로 거슬러 올라가면서 합친다면 문제가 해결됩니다.

 

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;

이 코드가 위의 설명을 코드로 작성한 것입니다.

 

이걸 코드로 작성한다면

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

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

이런식으로 작성할 수 있겠네요.

그렇다면 재귀는 언제 사용하면 좋을까요?

 

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

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

 

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

그러나 재귀를 적용할 수 있는 대부분의 경우에는, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.

 

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