재귀

컴퓨터/IT학습

lu

luasenvy (luasenvy)

재귀

function recursive() {
  // ... 코드
  recursive(); // 자기자신을 다시 호출
}

재귀_(再歸)는 한자처럼 말 그대로 다시 돌아가는 것을 말한다. 재귀함수로 많이 구현되며 함수내에서 자기자신을 호출하는 형태를 갖는다.

function factorial(n) {
  if (n === 1) return 1; // 탈출 조건
  return n * factorial(n - 1);
}

factorial(5);

가장 흔한 예시로 팩토리얼 계산을 구현하는 코드가 있다. 큰 문제를 더 작은 문제로 분해하여 해결할 수 있는 장점이 있다. 반복문들과 구조적으로 동일하기 때문에 무한루프에 빠지지 않도록 하는 탈출조건을 반드시 구현해야 프로그램이 오류없이 동작할 수 있다.

함수로써 콜 스택에 등록되며 실행되기 때문에 탈출조건이 올바르지 않거나 시스템 사양을 넘어서는 작업일 경우 Maximum Call Stack 오류를 만날 수 있으니 주의해야 한다.

// Error! Maximum Call Stack
function recursive() {
  // some code...
  const result = recursive();
  return result;
}

// Success
function recursive() {
  // some code...
  return recursive(); // 현재 함수가 Call Stack에서 비워지고 재귀 호출됨
}

재귀호출을 할 때에도 고려해야 할 것이 한 가지 있는데 return의 시점이다. 재귀 함수의 결과를 반환하도록 하면 콜 스택에서 비워지면서 다음 재귀를 실행하므로 메모리 사용량을 최소화 할 수 있다. 그러나 트리탐색과 같이 '다음 노드의 참조를 잃지 않기 위해' 현재의 재귀함수를 종료해서는 안되는 경우도 있으니 상황에 맞게 선택하여 사용해야한다.