재귀에 대한 전반적인 개념

알고리즘

재귀에 대한 전반적인 개념

nickbegain 2021. 7. 15. 09:29

- 재귀함수

→ 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 합니다

→ 재귀함수 활용

문제. 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 `arrSum을` 작성하세요.

[첫번째. 반복문을 이용하여 구현]

(자연수) 리스트의 합을 구하는 알고리즘

코드
function arrSum(arr) {

let sum = 0;

for (let i = 0; i < arr.length; i++) {

sum += arr[i];

}

return sum;

}

[두번째. 재귀함수 이용]

자연수의 리스트 [10, 3, 6, 2]의 합을 구한다고 가정합시다.

[10, 3, 6, 2]의 합을 구하는 건 신경쓰지 않고, 대신에 [3, 6, 2]의 합을 구하는 방법을 생각해 봅니다.
[3, 6, 2]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [6, 2]의 합을 구하는 방법을 생각해 봅니다.
똑같은 이유로 [6, 2] 대신 [2]의 합을 구하는 방법을 생각해 봅니다. [2]의 합에 6을 더해 [6, 2]의 합을 구할 수 있습니다.
[2]의 합을 구하는 건 매우 간단합니다. 2입니다.

이 과정을 아래의 간단한 코드로 표현할 수 있습니다.

arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);

arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);

arrSum([6, 2]) = 6 + arrSum([2]);

arrSum([2]) = 2 + arrSum([]);

arrSum([]) = 0;

arrSum을 아래와 같이 보다 엄밀하게(formally) 정의할 수 있습니다.

arrSum(arr)

1. arr이 빈 배열인 경우 = 0

2. 그 외의 경우 = arr[0] + arrSum(arr2)

(arr2는 arr의 첫 요소를 제외한 나머지 배열)

----------------------------------------------------------------------------------------------------------------

쪼개서 생각하는 방법

이처럼 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 합니다

재귀는 언제 사용하는 것이 가장 좋을까

→ 1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우

2. 중첩된 루프가 많거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우

→ 사실 모든 재귀 함수는 재귀 호출 없이 while / for loop으로 표현이 가능

→ 재귀를 사용 가능한 경우, 재귀를 사용한 코드가 대부분의 경우 더욱 간결하고, 일부의 경우에는 이해하기도 쉽습니다.

→ ‘하노이의 탑과 조합(combination) 문제’ (재귀함수 적용 문제)

Guide : 재귀적으로 사고하기

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

→ 재귀 함수를 통해 어떤 문제를 풀고자 하는 지, 즉 우리의 목표를 정리하는 데 도움이 됩니다. → 문제를 가장 추상적으로 또는 가장 단순하게 정리하는 것입니다.

[예] arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴합니다. 이를 좀더 간편하게 아래와 같이 표기한다고 가정합시다.

arrSum: [number] => number

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

→ 주어진 문제를 어떻게 쪼갤 것인지 고민합니다.

→ 어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해봅니다.

→ 일반적으로 입력값이 이 기준을 정하는 대상이 됩니다.

→ 이 때 중요한 관점은 순서와 크기입니다.

→ 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다.

[예] arrSum의 경우 입력값인 배열을 크기에 따라 구분할 수 있습니다. 그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절하다고 판단할 수 있습니다.
→ 이제 문제의 입력값에 따라 경우의 수를 나눕니다.

→ 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.

arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다르게 처리되어야 합니다.
arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])

3. 단순한 문제 해결하기

→ 문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결합니다.

→ 이를 재귀의 기초(base case)이라고 부릅니다.

→ 재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 됩니다.

arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0입니다.
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en])

4. 복잡한 문제 해결하기

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

arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
배열이 있을 때 head와 나머지 부분(tail)을 구분하는 방법만 안다면, arrSum을 해결할 수 있습니다.