누구나 알고리즘과 자료구조 10장 재귀를 사용한 재귀적 반복

10.1 루프 대신 재귀

루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다. 재귀가 빛을 발하는 예제를 살펴보자.

10.2 기저 조건

아래 함수의 경우 무한대로 음수를 출력한다.

function countdown(number) {
  console.log(number);
  countdown(number - 1);
}

영원히 지속되는 것을 막기 위해 조건문을 추가한다.

function countdown(number) {
  console.log(number);
  if (number === 0) {
    return;
  } else {
    countdown(number - 1);
  }
}

이처럼 모든 재귀 함수에는 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다.

10.3 재귀 코드 읽기

Factorial을 계산하는 예제를 살펴보자.

function factorial(number) {
  if (number === 1) {
    return 1;
  } else {
    return number * factorial(number - 1);
  }
}

재귀 코드가 어떻게 동작하는지 살피는 순서는 다음과 같다.

1. 기저 조건을 찾는다. number가 1일 때가 기저조건이다.
2. 기저 조건에서 함수가 어떻게 동작하는지 살핀다.
3. "끝에서 두 번째" 조건, 즉 기저 조건 바로 전 조건을 찾는다.
4. "끝에서 두 번째" 조건에서 함수가 어떻게 동작하는지 살핀다.
5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고, 그 때마다 함수가 어떻게 동작하는지 살핀다.

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

호출스택

컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다. 스택에는 가장 위 원소만 팝할 수 있다는 제약이 있다. 가장 위 원소는 가장 최근에 호출된 함수, 즉 컴퓨터가 다음으로 마무리해야 할 함수이니 이러한 제약은 재귀에 이상적이다.

이 방식을 ‘호출 스택을 통해 값 위로 전달하기'라고 부른다. 즉, 각 재귀 함수는 계산된 값을 보무 함수에 반환한다. 마침내 최초로 호출된 함수가 최종 값을 계산한다.

스택 오버플로우

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

10.5 파일시스템 순회

주어진 디렉토리의 모든 하위 디렉토리를 출력해야한다고 생각해보자.

• for문을 사용할 경우에 중첩된 for문 만큼만 하위 단계의 디렉토리를 출력한다.
• 재귀를 사용하면 2개, 3개, ... 단계의 하위 디렉토리까지 (더 이상 하위 디렉토리가 없을 때까지) 출력이 가능하다.

몇 단계나 깊이 들어가야 하는지 모르는 상황에서는 재귀가 자연스럽다.

오늘의 퀴즈

array = [
	1,
	2,
	3,
	[4, 5, 6],
	7,
	[8,
		[9, 10, 11,
			[12, 13, 14]
		]
	],
	[15, 16, 17, 18, 19,
		[20, 21, 22,
			23, 24, 25,
				[26, 27, 28, 29]
			], 30, 31
		], 32
]

배열 내 모든 숫자를 출력하는 재귀함수를 작성하라.

function printAllItems(array) {
	array.forEach(element => {
    if (Array.isArray(element)) {
      printAllItems(element);
    } else {
      console.log(element);
    }
  });
}