11장 재귀적으로 작성하는 법

• 이 챕터에서는 “재귀적으로 작성하는” 법을 쉽게 익힐 수 있는 몇 가지 비법을 배우게 된다.
• 11장에서는 재귀의 효율성은 논하지 않는다.
• 사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다.

1. 재귀 카테고리: 반복 실행

• 가장 쉬운 카테고리로, 반복적으로 한 작업을 실행하는 알고리즘이다.
• 10장에서 잠깐 훑어본 디렉토리 출력 알고리즘 역시 반복 실행 카테고리의 한 예다.

1.1 재귀 트릭: 추가 인자 넘기기

• 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 수행하려고 한다.
• 단 새 배열을 만드는 것이 아니라 배열 자체에서 수정하겠다.
  • 제자리(in-place) 수정
    • 데이터를 조작(변경)하는 기본적인 방식은 일반적으로 두 가지다.
    • 첫 번째 방법은 원래 배열은 그대로 두고 “두 배로 만든” 데이터로 이루어진 새 배열을 생성하는 것이다.
    • 두 번째 방법은 제자리(in-place) 수정이라 불린다. 실제 함수에 전달된 원본 배열을 바꾼다는 뜻이다.
    • 새 배열을 생성하든 원래 배열을 제자리에서 수정하든 선택은 사용자의 몫이고 프로젝트 상황에 따라 달라진다.
• 전형적인 루프처럼 인덱스를 기록하기 위해서는 함수를 수정하여 인수로 인덱스를 전달하게 만들면 된다.

2. 재귀 카테고리: 계산

• 하위 문제의 계산결과에 기반해 계산할 수 있을 때
• 하위 문제(subproblem)
  • 입력을 더 작게 한 똑같은 문제
  • factorial() 함수가 이에 해당한다.

2.1 두 가지 계산 방식

• 계산 함수를 작성하는 방식은 상향식(bottom up)과 하향식(top down) 두 방식이 있다.
• 두 방식 모두 재귀로 구현 가능하다.
• 그러나 상향식을 재귀로 작성하는 것은 그다지 간결하지 못하며 루프에 비해 이렇다 할 장점도 없다.
• 하지만 하향식은 재귀를 써야 한다. 하향식을 구현할 방법은 재귀뿐이다.
• 이것이 재귀가 강력한 도구로 자리잡게 된 이유이다.

3. 하향식 재귀: 새로운 사고방식

• 재귀는 하향식 방식을 구현하는 데 탁월하다.
• 하향식 사고방식은 **문제를 해결하는 새로운 사고 전략(mental strategy)**을 제공한다.
  • 즉, 문제를 완전히 다른 방식으로 생각하게 해 준다.
• 하향식으로 풀어 나갈 때는 머릿속에서 “문제를 뒤로 미루게” 된다.
• 하향식 factorial 구현의 핵심 줄을 보자.
  • 세부 사항은 하위 문제에서 다루게 두자.
• return number * factorial(number - 1)

3.1 하향식 사고 절차

• 하향식 문제를 풀 때 다음 사고 절차를 따라 생각하면 도움이 된다.

1. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.
2. 문제의 하위 문제를 찾자.
3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

3.2 배열 합

• 주어진 배열 내 모든 수를 합하는 sum이라는 함수를 작성한다고 하자.
• 가장 먼저 할 일은 sum 함수가 이미 구현되어 있다고 가정하는 것이다.
• 다음으로 할 일은 하위 문제를 찾는 것이다.
  • 이 예제의 하위 문제는 배열의 첫 번째 원소를 제외한 부분배열이다.

  return array[0] + sum(array[1, array.length - 1])
  

• 마지막으로 기저 문제를 처리한다.
  • 기저 조건: 배열에 원소가 하나만 남았을 때

4. 계단 문제

• 새로운 사고 전략을 사용해 하향식 재귀로 특정 계산 문제를 해결하는 법을 배웠다.
• 예제를 통해 더 자세히 알아보자.
• N개짜리 계단이 있고 누군가 한 번에 하나 혹은 둘, 세 계단까지 올라갈 수 있다고 하자. 계단 끝까지 올라가는 “경로”는 몇 개일까? N이 주어질 때 이를 계산하는 함수를 작성하라.
• 재귀적 사고방식을 취하지 않으면 이 계산을 수행하는 알고리즘을 이해하기 힘들다.
• 그러나 하향식으로 생각하면 문제가 놀랍도록 단순해진다.
• 11개짜리 계단을 올라가는 경우의 수는 몇 개일까?
  • 우선, 10개짜리 계단을 올라가는 하위 문제의 경우의 수가 필요하다.
  • 그럼 9개짜리 계단을 올라가는 하위 문제의 경우의 수도 필요하다.
  • 8개짜리 계단을 올라가는 하위 문제의 경우의 수도 필요하다.
  • 그럼 11개짜리 계단을 올라가는 경우의 수는 다음과 같다.
    1. 10개짜리 계단을 올라가는 경우의 수 → 마지막으로 계단 하나를 올라갈 때
    2. 9개짜리 계단을 올라가는 경우의 수 → 마지막으로 계단 두 개를 올라갈 때
    3. 8개짜리 계단을 올라가는 경우의 수 → 마지막으로 계단 세 개를 올라갈 때
  • 이외의 경우의 수는 존재하지 않는다.
• 즉, 이 문제의 답은 다음과 같다.
• number_of_paths(n - 1) + number_of_paths(n - 2) + number_of_paths(n - 3)

4.1 계단 문제 기저 조건

• 이 함수의 기저 조건은 다소 까다롭다.
• 주어지는 N에 따라 함수는 자기 자신을 0 또는 음수 N에 대해 호출할 수 있다.
• 이 조건을 구현하는 방식 중 하나는 기저 조건을 모두 하드코딩하는 것이다.
• return 0 if n <= 0 return 1 if n == 1 return 2 if n == 2 return 4 if n == 3
• 다른 한 가지는 시스템을 영리하게 조작할 이상하지만 효과적인 기저 조건을 고안하는 것이다.
• return 0 if n < 0 return 1 if n == 1 || n == 0

5. 애너그램 생성

• 애너그램이란 문자열 내 모든 문자들을 재배열한 문자열이다.
• 문자열의 모든 애너그램을 구해 보자.
• 이 문제를 하향식 사고방식으로 접근해 보자.
• 예를 들어, 문자열 “abcd”의 애너그램을 모두 구해 보자.
• “abc”는 이 문제의 하위 문제가 될 수 있다.
• 그렇다면 “abc”의 모든 애너그램을 반환하는 anagram 함수가 있을 때 이를 어떻게 사용해서 “abcd”의 모든 애너그램을 만들어낼 수 있을까?
• “abc”의 각 애너그램 내 가능한 자리마다 “d”를 붙여 “abcd”의 모든 애너그램을 만들어 낼 수 있다.

5.1 애너그램 생성의 효율성

• 애너그램 생성 알고리즘의 효율성을 분석해 보자.
• 문자열 4개: 애너그램 4 * 3 * 2 * 1
• 문자열 5개: 애너그램 5 * 4 * 3 * 2 * 1
• 문자열 6개: 애너그램 6 * 5 * 4 * 3 * 2 * 1
• 즉, N!이다.
• O(N!)
• 이를 계승 시간factorial time이라고도 부른다.
• 이는 매우 느리지만(O(2^N))보다 느리다) 모든 애너그램을 생성해야 하는데 문자 N개로 된 단어에는 애너그램이 N!개이니 더 나은 방법은 없다.

6. 마무리

• 재귀는 다양한 문제를 해결하는 훌륭한 도구이지만 주의 깊게 사용하지 않으면 코드가 현저히 느려진다.
• 다음 장에서는 재귀를 사용하되 코드를 깔끔하고 빠르게 유지시키는 법을 배운다.