누군가는 재귀를 자전거를 타는 것에 비유하기도 합니다. 다른 사람이 타는 것을 옆에서 지켜보면 꽤 쉬워 보이는데 막상 내가 타려고 하면 생각보다 잘 안 됩니다. 자전거를 잘 타는 방법은 계속 시도하고 연습하는 수밖에 없습니다. 재귀 역시 마찬가지입니다. 자연스러워질 때까지 연습해야 합니다.
재귀 함수를 통해 어떤 문제를 풀고자 하는 지, 즉 우리의 목표를 정리하는 데 도움이 됩니다. 문제를 가장 추상적으로 또는 가장 단순하게 정리하는 것입니다. arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받아서 number를 리턴합니다. 이를 좀더 간편하게 아래와 같이 표기한다고 가정합시다.
arrSum: [number] => number주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해봅니다. 일반적으로 입력값이 이 기준을 정하는 대상이 됩니다. 이 때 중요한 관점은 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기를 기준으로 구분할 수 있거나, 순서를 명확하게 정할 수 있는지를 살펴보는 것이 도움이 됩니다. 그리고 구분된 문제들을 푸는 방식이 같다면, 문제를 제대로 구분한 것입니다.
arrSum의 경우 입력값인 배열을 크기에 따라 구분할 수 있습니다. 그리고 arrSum([1, 2, 3, 4])를 구하는 방법과 arrSum([2, 3, 4])을 구하는 방법은 동일할 것이므로 이 구분은 적절하다고 판단할 수 있습니다.
이제 문제의 입력값에 따라 경우의 수를 나눕니다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.
arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다르게 처리되어야 합니다.
arrSum: [number] => numberarrSum()arrSum([e1, e2, ... , en])
문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다. 재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 됩니다.
arrSum를 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이 때 arrSum은 0입니다.arrSum: [number] => numberarrSum() = 0arrSum([e1, e2, ... , en])남아있는 복잡한 경우를 해결합니다.
arrSum이 길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더합니다.arrSum: [number] => numberarrSum() = 0arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])