JS => 재귀함수

재귀함수

1. 어떠한 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법을 "재귀" 라고 한다.
2. 함수가 자기 자신을 호출하는 경우 '재귀함수' 라고 한다.
3. 반복되는 중첩 횟수를 모를 때 사용하며 좋다.

재귀함수를 이용할 때, 중점!
1. 탈출조건: 언제 재귀 루프를 탈출할 것인가 (Base case)
2. 호출지점: 재귀호출 지점을 어디로 정할 것인가
3. 모든 경우의 수를 따지고 있는가

---

재귀함수 템플릿

1. Base case

더 이상 쪼갤 수 없는 결과값을 제시 (탈출 조건)

2. Recursive case

목표한 값을 얻기 위해 탈툴 조건에 도달할 때까지 이어지는 동작

3. 일반적인 재귀함수 템플릿

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

4. Recursion Depth

가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수.
깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 동일.

---

재귀함수와 메모리 사용량 간의 관계

단점: 메모리
1. 보통 재귀함수는 함수의 호출이 반복적으로 이루어지기 때문에 메모리 요구사항에 유의해야 한다.
2. 중첩된 깊이(depth)가 크다면 depth 만큼 실행 컨텍스트가 저장될 메모리 공간이 필요하기
때문에, 반복문 기반 알고리즘을 통해 메모리 비용(=함수 호출 비용) 절약이 가능하다.

장점: 가독성과 변수 사용량 감소
1. 알고리즘 자체가 재귀적으로 표현하는게 가독성이 좋을 때.
2. 재귀함수로 변수 사용량을 줄여 오류 발생 확률을 낮출 수 있다.

---

꼬리재귀

꼬리재귀란,
재귀호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태이다.
아래 예시를 참고하는게 더 이해하기 편할 것이다.

일반적인 재귀함수

function fac(n){
  if(n === 1){
    return n;
  }
  return n*fac(n-1);
}

꼬리재귀

function fac(n){
  if(n === 1){
    return n;
  }
  let result = fac(n-1); // 재귀 함수 결과를 변수에 저장
  return n*result;
}

위 예시의 결과는 똑같이 나온다.
하지만 일반적인 재귀함수는 리턴 값이 함수이기 때문에 계속 호출을 통해 스택이 쌓인다.
꼬리재귀의 경우는 해당 함수호출을 변수에 할당하여 추가 연산이 일어나지 않아,
스택이 계속 쌓이는 재귀의 단점을 보완한다.