재귀의 이해 - 다르게 생각하기

이번 시간의 목표는 이 방법을 학습하고 연습하면서 다양하게 생각하는 능력을 기르는 것입니다.

새로운 문제 해결 방법을 배우기 전에, 아래의 간단한 코딩 문제를 해결해 봅시다.

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

• (자연수) 리스트의 합을 구하는 알고리즘
  1. 보조 변수 sum을 0으로 초기화한다.
  2. 순차적으로 리스트의 구성요소에 접근하면서 sum에 더한다.
• 코드

    function arrSum(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i]; } return sum;
    }

이제 이 문제를 다른 각도에서 생각해 보겠습니다.자연수의 리스트 [10, 3, 6, 2]의 합을 구한다고 가정합시다.

1. [10, 3, 6, 2]의 합을 구하는 건 신경쓰지 않고, 대신에 [3, 6, 2]의 합을 구하는 방법을 생각해 봅니다.

• [10, 3, 6, 2]보다는 [3, 6, 2]가 더 작으니 왠지 더 쉽게 풀릴 것 같기도 합니다. [3, 6, 2]의 합을 구하는 방법을 알아낸다면, 이 값에 10을 더하면 원래의 목적인[10, 3, 6, 2]의 합을 구할 수 있습니다.

2. [3, 6, 2]의 합을 구하는 것도 조금 버겁게 느껴져서, 대신에 [6, 2]의 합을 구하는 방법을 생각해 봅니다.

• 똑같은 이유로 [3, 6, 2]보다는 [6, 2]가 더 작아서 쉽게 풀 수 있을 것 같습니다. [6, 2]의 합을 구하는 방법을 알아낸다면, 이 값에 3을 더하면 [3, 6, 2]의 합을 구할 수 있습니다.
• arrSum([3, 6, 2]) = 3 + arrSum([6, 2])

3. 똑같은 이유로 [6, 2] 대신 [2]의 합을 구하는 방법을 생각해 봅니다. [2]의 합에 6을 더해 [6, 2]의 합을 구할 수 있습니다.

4. [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;

쪼개서 생각하는 방법

이처럼 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀(recursion)라고 합니다. 재귀의 과정을 arrSum에 적용해보면 아래와 같습니다.

1. 원래의 문제에서 출발하여 더 작은 경우를 생각합니다.

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

2. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각합니다.

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

3. 이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결합니다.

        arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
        // 가장 작은 경우의 해결책을 적용한다.
        arrSum([2]) = 2 + arrSum([]) = 2;
        arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
        arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
        arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;

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

    arrSum(arr)
    1. arr이 빈 배열인 경우 = 0
    2. 그 외의 경우 = arr[0] + arrSum(arr2) (arr2는 arr의 첫 요소를 제외한 나머지 배열)

만약에 arrSum 함수를 javascript 코드를 구현할 경우 (코플릿 과제 중 하나입니다), arrSum은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출하기도 합니다. 이러한 호출 방식을 재귀 호출이라고 합니다.