재귀함수는 자기 자신을 호출하는 함수를 뜻합니다
* 재귀: 원래의 자리로 되돌아가거나 되돌아오는 것을 말한다.
재귀함수를 사용할 때는 꼭 두 경우가 있어야하는데,
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병을 받을 것이다.
내가 마신 콜라의 총 갯수는 몇 병일까?
빈명 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. 재귀함수
함수자체가 크게 반복문의 역할을 한다
베이스 조건 만들기 및 리턴 타입 확인하기
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)
```