재귀로 문제 해결하기

재귀란 무엇인가?

자기 자신을 호출하는 함수로서, 어떤 문제를 동일한 종류의 더 작은 문제로 나누고 그 작은 문제를 해결하는 것을 말한다. 점차적으로 문제는 더 이상 나눠지지 않고 명확하며 재귀적이지 않도록 프로그래머에 의해 정의된 해결책을 갖는 Base case가 될 것이다.

왜 재귀를 사용하는가?

문제를 더 간단하게 분해할 수 있다. 문제의 가장 단순한 부분 더 이상 나눌 수 없는 Base case로 문제를 분해하고, 하위 문제로 분해하여 문제를 간단하게 생각할 수 있다.

어떻게 재귀를 사용하는가?

재귀에 대한 최상의 접근 방법은 Base case를 구별하고 처리하기 쉬운 작은 단위로 문제를 어떻게 나눌 수 있는가에 대해 생각하는 것이다. 올바른 Base case와 하위 문제를 결정했다면 일어날 수 있는 모든 것들에 대해 자세히 생각할 필요가 없다. 하위 문제에 대한 해결책이 옳다면, 하위 문제에 대한 해결 방법들로부터 최종 해결책을 만들 수 있을 것이다.

예제로 숫자들 중에 최댓값을 구하는 예제를 재귀로 작성해보자. 아마도 대부분 사람들은 최댓값을 담는 변수를 두고 리스트의 모든 요소에 대한 루프를 돌아서 최댓값을 구하는 방법을 생각할 것이다.

const numbers = [1, 5, 10, 7, 13, 9, 2];

let max = 0;
for (let i = 0; i < numbers.length; i++) {
  if (numbers[i] > max) {
    max = numbers[i];
  }
}

console.log(max); // 13

재귀적으로 문제를 푼다면 먼저 베이스 케이스를 정의해야 한다. 요소가 하나밖에 없는 목록에서는 그 요소가 최댓값이다. 둘 이상의 목록에서는 어떻게 해야 할까? 목록의 첫 번째 요소와 나머지 목록에서의 최댓값과 비교해서 큰 값을 반환한다.

const maximum = (numbers) => {
  if (numbers.length === 1) {
    return numbers[0];
  }

  return Math.max(numbers[0], maximum(numbers.slice(1)));
}

console.log(maximum([1, 5, 10, 7, 13, 9, 2])); // 13

피보나치 수열에서는 Fib(0) = 0, Fib(1) = 1이 베이스 케이스다. 그리고 모든 1보다 큰 숫자들에 대해서 하위 문제인 Fib(n) = Fib(n - 1) + Fib(n - 2)로 분해할 수 있다.

Source

• 가장 쉬운 하스켈 책 4장 재귀 http://www.kyobobook.co.kr/product/detailViewKor.laf?barcode=9788994774619