10장 재귀를 사용한 재귀적 반복

• 재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다.

1. 루프 대신 재귀

• 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.
• 재귀를 쓸 수 있다고 해서 무조건 재귀를 써야 한다는 것은 아니다.
• 재귀는 명쾌한 코드를 작성할 수 있는 하나의 도구다.

2. 기저 조건

• 기저 조건(base case): 함수가 반복되지 않는 경우
• 모든 재귀 함수에는 함수가 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다.

3. 재귀 코드 읽기

• 재귀 코드를 읽는 방법
  1. 기저 조건을 찾는다.
  2. 기저 조건에서 함수가 어떻게 동작하는지 살펴본다.
  3. “끝에서 두 번째” 조건을 찾는다. 곧 보이겠지만 이는 기저 조건 바로 전 조건이다.
  4. “끝에서 두 번째” 조건에서 함수가 어떻게 동작하는지 살펴본다.
  5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그 때마다 함수가 어떻게 동작하는지 살핀다.
• 기저 조건부터 분석을 시작해서 나아가는 것은 재귀 코드를 추론하는 훌륭한 방법이다.

4. 컴퓨터의 눈으로 바라본 재귀

• 컴퓨터에서 재귀는 까다롭다.
• 아직 factorial(3) 을 다 실행하지 않았는데 factorial(3) 을 실행하는 중에 factorial(2) 실행을 시작해야 한다.

4.1 호출 스택

• 9장 스택과 큐로 간결한 코드 생성에서 스택을 배웠다.
• 컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다.
• 이 스택을 목적에 딱 맞게 호출 스택(call stack)이라 부른다.
• 스택에는 가장 위의 원소만 pop할 수 있다는 제약이 있다.
• 가장 위의 원소는 가장 최근에 호출된 함수, 즉 컴퓨터가 다음으로 마무리해야 할 함수이니 이런 제약은 재귀에 이상적이다.
• 마지막에(즉 가장 최근에) 호출했던 함수를 가장 먼저 완료해야 하므로 LIFO와 맞아 떨어진다.
• factorial 함수는 재귀에 기반해 이루어지는 계산이다.
  • factorial(1)이 자신의 결과를 factorial(2)에 전달하고, factorial(2)가 자신의 결과를 factorial(3)에 전달함으로써 이뤄진다.
  • 이러한 방법을 호출 스택을 통해 값 위로 전달하기 라고 부르기도 한다.
    • passing a value up through the call stack
    • 각 재귀 함수는 계산된 값을 “부모”함수에 반환한다.

4.2 스택 오버플로우

• 무한 재귀에서는 컴퓨터가 반복해서 같은 함수를 호출 스택에 푸시한다.
• 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 호출 스택은 점점 늘어난다.
• 결국 스택 오버플로우stack overflow라는 오류가 발생한다.

5. 파일시스템 순회

• 재귀와 잘 맞는 문제 유형은 몇 단계나 깊이 들어가야 하는지 모르는 상황에서 문제를 여러 단계로 파고 들어야 할 때다.
• 파일 시스템을 순회하는 예제를 살펴보자.
  • 디렉토리의 하위 디렉토리, 그 하위 디렉토리에 하위 디렉토리가 또 있으면 동일한 작업을 수행해야 할 때
  • 18절에서 다시 한 번 살펴본다.

6. 마무리

• 알고리즘이 임의의 단계만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다.