recursion: 함수 자신을 리턴하는 함수
입력값이나 문제의 순서를 고려하여, 문제를 쪼갤 수 있을 때까지 쪼깬다.
모든 재귀는 for
문이나 while
로 구현할 수 있다. \그러나 중첩의 횟수가 감당할 수 없는 정도로 많을 경우, 식이 매우 복잡해 진다.
수학의 계승(factorial)을 재귀로 연습해 볼 수 있다. 위에 언급처럼 이 문제는 for
문이나 while
로 구현할 수 있지만, 재귀로 풀어보자.
문제) 5!(factorial)의 값?
함수(1) ⇒ 1 이다. 쪼갤 수 있는 마지막 케이스이다. 위 식은 재귀함수를 호출하여 값을 구한다.
function fac(num) {
if (num <= 1) {
// num이 1보다 작거나 같을 때 1이 나와야 5 factorial의 마지막 수, 즉 1이 나올 수 있다.
return 1
} // 이 식은 base case이며 재귀 탈출을 하도록 한다.
return num * fac(num - 1)
// 5 * fac(4)
// fac(4) = 4 * fac(3)
// fac(3) = 3 * fac(2)
// fac(2) = 2 * fac(1)
// fac(1) = 1
러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.
number
타입의 수boolean
타입const matryoshka = {
size: 10,
matryoshka: {
size: 9,
matryoshka: null,
},
};
let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true
output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false
1) 가장 작게 쪼갤 수 있는 식은 마지막 matryoshka 객체의 size의 값을 찾는 식이다.
1-1) if (matryoshka.size === size) { return true }
라는 base case를 정한다.
2) 위의 경우 아닌 경우 내부 객체의 size를 비교하는 재귀 호출을 넣도록 한다. 단, 내부 객체의 값이 존재하고, 찾고자 하는 size가 내부 객체의 size보다 작아야 한다.
2-1) else if (matryoshka.matryoshka && matryoshka.size > size)
{return findMatryoshka(matryoshka.matryoshka, size)
라는 recursive case를 정한다.
3) 위 모든 경우가 아닌 경우, 즉 size나 아무 객체에도 발견되지 않는 경우 false
를 반환하도록 한다.
3-1) return false
function findMatryoshka(matryoshka, size) {
if (size === matryoshka.size) {
return true;
} else if (matryoshka.matryoshka && matryoshka.size > size) {
return findMatryoshka(matryoshka.matryoshka, size)
}
return