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

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

문제. 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 `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은 (인자가 빈 배열이 아닌 경우) 실행과정 중에 자기 자신을 호출하기도 합니다. 이러한 호출 방식을 재귀 호출이라고 합니다.