재귀함수 심화

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

---

재귀함수는 함수의 호출이 반복적으로 이뤄지기 때문에 성능에 좋지 않고,
스택 오버플로우 - 프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도하여 프로그램 충돌이 발생하는 것 - 의 원인이 됨

재귀함수를 쓰는 이유

• 가독성을 위함
• 변수 사용량을 줄임 - 변경가능한 상태를 제거하여 오류 발생 확률을 낮춤

꼬리 재귀

---

재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 재귀의 형태

*일반 재귀 함수

function add(num){
  if(num===0)return 0;
  
  return num + add(num-1)
}

• 꼬리 재귀 함수

function add(num){
  if(num===0)return 0;
  
  let result = add(num-1);
  return num + result;
}

결과는 같으나 일반 재귀 함수는 스택이 계속 쌓이고,
(리턴값이 함수이기 때문에 계속해서 함수 호출)
꼬리 재귀 함수는 한 번만 호출됨
(함수를 호출하여 그 함수를 변수에 할당하여 사용)

하노이의 탑 재귀

---

3개의 기둥과 크기가 다른 N개의 원판이 주어졌을 때 1번 기둥의 모든 원판을
3번 기둥으로 옮기는 퍼즐게임

=> 2**N -1 번의 움직임으로 해결

const answer = [];

const hanoi = (n, a, b, c) =>{
  if(n===1) answer.push([a,c])
}else{
  hanoi(n-1, a, b, c);
  answer.push([a,c]);
  hanoi(n-1, b, c, a);
  }
}

function solution(n){
  hanoi(n, 1, 3, 2);
  
  return answer;
}

조합 재귀 함수

---

1. 순열 nPr
   서로 다른 n개 중 r개를 뽑을 때 순서를 포함한 경우의 수

2. 조합 nCr
   서로 다른 n개 중 r개를 뽑을 때 순서에 상관없이 뽑는 경우의 수
   만일 중복 가능한 n 개중 r 개를 뽑으면 중복 조합

3. 조합 점화식 nCr = n-1Cr-1 + n-1Cr
   1) n-1Cr-1 = 어떤 특정한 원소를 포함하고 뽑았을 때
   특정한 원소 1개를 이미 뽑았다고 가정하면 n-1개가 남아있고,
   이미 1개를 뽑았으므로 r-1개 뽑을 수 있음

   2) n-1Cr = 어떤 특정한 원소를 포함하지 않고 뽑았을 때
   특정한 원소 1개를 포함하지 않고 n-1개에서 r개를 뽑아야함

   위의 두 가지 경우를 합해야 nCr

4. 조합의 갯수 nCr = n!(r!*(n-r)!)

const oneSize = 1;
function getCombinationSize(n,r){
  if(n===r || r ===0) return oneSize;
  else return getCombinationSize(n-1,r-1) + getCombinationSize(n-1,r)
}