재귀

Ramne·2021년 7월 20일

Achievement Goals
✅ 재귀의 의미에 대해서 이해하고, 자바스크립트에서 재귀 호출을 할 수 있다.
✅ 재귀를 언제 사용해야 하는지 알고 있다.
✅ 재귀 함수를 base case와 recursive case로 나눠서 작성할 수 있다.
✅ 자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
✅ 실생활에 사용되는 유용한 Tree 구조를 알고 있다.
✅ 깊이를 알 수 없는 Tree 구조를 재귀 함수로 모두 순회(traverse)할 수 있다.

재귀(recursion)

어떤 문제를 해결할 때, 동일한 구조의 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법

재귀 호출
실행 과정 중 자기 자신을 호출하는 것

재귀는 언제 사용할까?

주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀함수 vs 반복문

반복문은 동일한 변수를 반복적으로 사용하기에, 함수를 새로 호출할 필요가 없다.
따라서 context switching 비용이 발생하지 않기 때문에, 속도가 빠르다.
하지만 for 문은 여러 변수를 선언해야해서 재귀에 비해 코드가 더 긴 경우가 많다.

재귀 함수는 동일 함수를 반복 호출하니 변수를 여러개 만들 필요가 없어, 코드가 간결하다.
하지만 지속적인 함수 호출로 발생하는 데이터를 프로세스의 Stack에 저장해야하기 때문에 이는 선언한 변수의 값만 변경해서 사용하는 반복문과 달리 많은 메모리 사용을 야기한다.

또, 함수 호출과 복귀를 위한 context switching 비용이 발생하기 때문에,
속도가 상대적으로 느리다. 즉, 오버헤드가 발생하여 속도가 느려진다.

재귀 함수의 단점 해결 방법 ; 꼬리 재귀

컴파일러가 꼬리 재귀 코드를 보고, 적절한 반복문으로 컴파일 하는 방식.

단, 꼬리 재귀는 return 문에 연산이 없는 경우에만 적용된다.
리턴문에 함수만 있다면 꼬리 재귀지만, 그 경우가 아니면 꼬리 재귀로 컴파일 할 수 없다.

function sumTo(num, acc = 0) { // 초기 누적값 0
  if (num === 0) return acc // base recursion
  return sumTo(num - 1, acc + num) 
}

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기

재귀적으로 사고하는 데에 가장 먼저 해야 할 일은
문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것

2. 문제를 쪼개고 경우의 수를 나누기

문제를 쪼갤 기준을 정하고, 정한 기준에 따라 더 큰 경우와 작은 경우로 구분할 수 있는지 확인.
이때 중요한 관점은 입력값이나 문제의 순서와 크기.
문제에서 주어진 입력값에 따라, 경우의 수를 나눈다.
일반적으로 문제를 더 이상 쪼갤 수 없는 경우, 그렇지 않은 경우로 나눈다.

3. 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다.
이를 재귀의 기초(base case)이라고 부릅니다.
재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성.

4. 복잡한 문제 해결하기

남아있는 복잡한 경우(recursive case)를 해결.

재귀 함수 기본 템플릿

function recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

재귀 함수 예시

function 맛집찾기(위치) {
  // base case
  if(맛집의 조건) return 맛집 // 재귀 탈출의 기본 조건
  
  // recursive case
  for (let i ~ 반복문) {
    if(저쪽 동네에는 맛집이 있을까?) {
      let 찾았다 = 맛집찾기(저쪽 동네);
      if (찾았다) return 찾았다
    }
  }
}

왜 재귀함수를 바로 리턴하지않고 변수에 담아 조건문을 통과 한 후 리턴을 할까?
재귀함수를 바로 리턴할 경우는 조건을 만족한 리턴값 뿐만 아니라,
조건을 충족하지 못한 undefined 또한 반환될 수 있다.
따라서, 도중에 포기하지 않고 정말 찾았을 경우만을 리턴하기 위해서이기도 하고
조건에 부합하는 것을 찾고 난 후에도 실행되는 불필요한 재귀를 멈추기 위해서도 쓴다.