재귀함수

재귀함수

재귀는 컴퓨터 과학의 핵심 개념이다. 재귀는 함수가 자기 자신을 호출할 때 쓰는 용어다. 무한 재귀는 쓸모없다. 올바르게 사용하면 강력한 도구가 될 수 있다.

루프 대신 재귀

10을 받ㄷ아 10부터 0까지 숫자를 표시하는 함수

function countdown(number){
  for(let i = number; i>= 0; i--){
   console.log(i);
  }
}
countdown(10)

재귀를 쓴다면

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

루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.

기저 조건

countdown(0) 을 하게 되는 경우 음수를 무한대로 출력하므로 완벽하지않음. number가 0이면 더이상 countdown()을 호출하지 않는 조건문을 추가해 문제를 해결할 수 있다.

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

재귀에 쓰이는 용어로 함수가 반복되지 않는 이러한 경우를 기저조건이라 부른다. 예제의 countdown() 함수는 0이 기저조건이다.. 모든 재귀 함수에는 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야한다.

재귀 코드 읽기

재귀 코드는 어떻게 읽어야하는가?

계승(factorial)을 게산하는 예제를 살펴보자.

컴퓨터는 어떻게 이러한 정보를 다 기록할까? factorial(1)이 끝나면 다시 돌아가 factorial(2)를 마저 실행해야 하다는 사실을 어떻게든 기억해야한다.

또한 factorial(2)를 끝낸 후 factorial(3)을 완료해야 한다는 사실도 기억해야한다.

호출 스택

9장 스택과 큐로 간결한 코드 생성에서 스택을 배웠다. 컴퓨터는 스택을 사용해 어떤 함수를 호출 중인지 기록한다. 이 스택을 목적에 맞게 호출 스택(call stack) 이라고 부른다.

스택에는 가장 위 원소만 팝할 수 있다는 제약이 있다. 가장 위 원소는 가장 최근에 호출된 함수, 즉 컴퓨터가 다음으로 마무리해야할 함수이니 이러한 제약은 재귀에 이상적이다. 마지막(즉, 가장 최근에) 호출했던 함수를 가장 먼저 완료해야 하므로 LIFO와 맞아 떨어진다.

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

아까 무한 재귀 예제의 호출 스택은 어떻게 될까? 무한 재귀에서는 컴퓨터가 반복해서 같은 함수를 호출 스택에 푸시한다. 단기 메모리에 더이상 데이터를 저장할 공간이 없을 때까지 호출 스택은 점점 늘어난다. 결국 스택 오버플로라는 오류가 발생한다. 컴퓨터는 재귀 강제로 중단하고. 메모리가 다 찼으니 함수 호출을 거부한다! 고 외친다.

파일 시스템 순회

재귀와 자연스럽게 들어맞는 한 가지 문제 유형은 몇 단계나 깊이 들어가야하는지 모르는 상황에서 문제를 여러 단계로 파고 들어야 할 때다.