재귀함수란?

---

재귀함수는 자기 자신을 호출하는 함수를 뜻합니다
* 재귀: 원래의 자리로 되돌아가거나 되돌아오는 것을 말한다.

재귀함수를 사용할 때는 꼭 두 경우가 있어야하는데,

1. base case: 더이상 문제를 쪼갤 필요가 없는 종료된 경우
2. recursive case: 문제를 쪼개서 풀어가는 경우

e.g

function f(n) {
	if (n <= 1) { // base case
    return 1
    }
  return n + f(n-1) // recursive case
}

참고 자료

재귀함수는 언제 사용하면 좋을까요?

1. 주어진 문제를 비숫한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측하기 어려운 경우
3. 이 밖에도, 알고리즘 문제의 많은 부분(코테, 알고리즘 테스트, 직무 면접 등)

참고 자료

알고리즘 문제를 활용한 예시를 보자!

콜라 빈명 2개를 가져가면 > 새것 1병으로 교환해준다 나는 총 빈병 20개를 가지고 있다. → 그럼 새것 10병을 받을 것이다.
10병을 그자리에서 마신다 → 그럼 새것 5병을 받을 것이다.
5병을 그자리에서 마신다 → 그럼 새것 2병을 받을 것이다. + 빈병 1개가 남을 것이다.
2병을 그자리에서 마신다  → 그럼 새것 1병을 받을 것이다. 
새병 1개 마셔버리고 + 아까있던 빈병 1개 → 새것 1병을 받을 것이다.
내가 마신 콜라의 총 갯수는 몇 병일까?

1. 빈명 20개에서 2병당 1개로 교환하는 조건 > 빈병 n개에서 a병당 b개로 교환하는 조건으로 어떤 수를 넣어도 계산해주는 함수를 짜야한다.

   a. while문

   function solution(a,b,n) {
   	let 새콜라 = 0;
     	let 빈병 = n;
     
     while(Math.floor(빈병 / a) > 0) {
     	let 교환한콜라 = Math.floor(빈병 / a)*b;
       빈병 = 교환한콜라 + Math.floor((빈병) % a);
       새콜라 += 교환한콜라;
     }
     return 새콜라
   }

   b. 재귀함수

   1. 베이스 조건 만들기
   2. 리턴 타입을 확인하기
   3. 베이스 조건에 가까워질 수 있도록 매개변수의 값을 서서히 줄이면서 연산하기
   4. 한단계 위, 3단계 위 정도까지 값이 잘 돌아가는지 테스트 해보기

   함수자체가 크게 반복문의 역할을 한다
   베이스 조건 만들기 및 리턴 타입 확인하기
   if문으로 베이스조건(종료 조건)을 먼저 지정하고, 종료 조건에 도달하면 계산 완료된 새콜라의 갯수(리턴 타입)을 반환하면서 함수가 종료된다

   베이스 조건에 가까워질 수 있도록 매개변수의 값을 서서히 줄이면서 연산하기
   교환한 콜라와 빈병, 새콜라의 계산식은 while 문과 똑같다
   종료 조건에 도달할 수 있도록 빈병이 점차 줄어들 것이고,
   리턴을 할 때 줄어든 빈병을 매개변수로 넣고 다시 재귀함수를 호출한다

   let 새콜라 = 0;
   
   function recursive(a, b, 빈병) {
   	if(빈병 < a) {
       	return 새콜라; 
       } // 베이스 조건(종료 조건)
     
     let 교환한콜라 = Math.floor(빈병 / a) * b;
     빈병 = 교환한콜라 + Math.floor((빈병) % a);
     새콜라 += 교환한콜라;
     return resursive(a, b, 빈병);
   }

return recursive(a, b, n)

```

참고 자료