재귀 : "도르마무 거래를 하러왔다..."

재귀함수

: 자기 자신을 호출하는 함수

• 재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴

1. 재귀함수 필요성

• 반복문은 재귀함수로 구현 가능
• 반복문으로 작성했을 때 복잡한 코드를, 재귀함수로 구현 시 간결해짐
• 중첩된 반복문이 많거나 횟수를 예측하기 어려울 때, 재귀함수가 가독성이 더 나으므로 사용하기 적합하다.
• 한 작업을 => 비슷한 구조로 더 작은 단위의 작업으로 나눌 수 있을 때 사용

2. 재귀함수 사용처

1. 복잡한 데이터 구조, 알고리즘의 해결 방법으로 재귀가 사용되곤 한다.

2. JSON.parse / JSON.stringify
   JSON.stringify : 모든 타입을 문자열로 바꿔준다.

• <예시>

  JSON.stringify({key : "value"}) 
  // 결과값 '{"key":"value"}'

  객체의 요소들(key, value)을 반복하여 JSON.stringify(문자열화) 해주기 때문에 재귀함수를 사용하는 예다.
  *브라우저 엔진에서 JSON 타입은 보통 재귀를 사용

3. DOM Tree UI
   document.getElementById 와 DOM 순회 알고리즘들.
   DOM은 트리 구조로 중첩 구조가 많다. 많이 반복되는 중첩구조를 탐색할 때 재귀를 사용할 수 있다.

4. Object를 순회할 때 사용하기도 한다. (for문 역할)

3. 재귀를 잘못 사용하는 경우

1. 잘못된 것을 return하거나 return 을 안해준 경우
2. base case(탈출 조건) 없는 경우

• 스택 오버플로우(stack overflow)
  함수를 호출 시 call stack에 쌓인다. 그런데 탈출 조건이 없어서 함수를 종료하지 않고 재귀함수 호출을 무한반복 한다면, call stack에 메모리가 쌓인다. 크롬엔진에서는 call stack 사이즈의 한계치를 넘기면 에러를 출력한다. Maximum call stack size exceeded 이라는 에러가 발생하고 이를
  스택 오버플로우(stack overflow)라고 한다.

• 단점
  재귀함수는 호출할 때마다 스택을 소비하기 때문에 반복문에 비해 시간이 많이 소요된다.

//<예시> 탈출조건이 없는 재귀함수
function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

• 위 코드 실행시 나오는, call stack 사이즈의 한계치를 넘겼다는 에러.
  

4. 재귀함수 구성요소

1. base case

• 재귀함수 종료시점. 더이상 안 쪼개질 때 탈출하는 조건이다.

2. recursive case

• 문제를 작은 단위로 쪼개는 작업.
• 재귀함수 호출 시, 매 번 다른 데이터가 입력되어야 한다.

문제1. 배열의 합 구하기

자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 arrSum 을 작성하세요.

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  // base case : 가장 작은 문제를 해결하는 코드, 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0;
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  // recursive case : 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr);
  
  //arr.shift() : 첫번째 요소를 제거하고 제거된 요소를 반환
  //arr는 첫번째 요소가 제거된 상태다.
}

• 푸는 순서

1. 입출력값 정의하기

2. 문제를 쪼개고, 입력값이 빈 배열인 경우와, 아닌 경우를 나눈다

3. base case (가장 작은 문제 해결, 재귀 탈출 코드)
   더이상 안 쪼개질 때 탈출하는 조건.
   입력값이 빈배열인 경우 0을 리턴

4. recursive case (재귀함수로 문제 쪼개나가는 코드)

   function arrSum(arr) {
     // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
     if (arr의 길이가 0인 경우) {
       return 0;
     }
   
     // recursive case : 그렇지 않은 경우
     return 요소1 + arrSum([요소2, ... , 요소n]);
   }

   
   

재귀함수 템플릿

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

문제2. factorial

<입력값 = n>
5 * 4 * 3 * 2 * 1
= 5 * 4!   (첫번째 요소n * n-1 재귀함수)
= 5 * 4 * 3! 

<참고사항>
0! === 1
1! === 1

function fac(n){
    if (n <= 1) return 1;
    return n * fac(n-1);    // 5 * 4!
}
fac(5);

---

꼬리 재귀 Tail Call Optimization

• 재귀 문제점 : 메모리를 많이 차지하여 성능이 반복문에 비해 느림
• 해결방법 : 꼬리 재귀
  ECMAScript 6의 꼬리 호출 최적화

꼬리 재귀는 재귀의 문제점을 해결할 수 있는 방법이다.
call stack 사이즈를 잡아먹지 않는 최적화 방법이라고 한다.

하노이의 탑 재귀 (js tower of hanoi in recursion)

조합 재귀 함수 (js combination in recursion)

참고

[JS 알고리즘] 재귀(Recursion) - jangws