▷ 재귀함수란?
재귀(再歸): 원래의 자리로 되돌아가거나 되돌아옴.
재귀를 사용하면 반복문인 for, while을 사용하지 않고, 간결한 코드를 짤 수 있다.
❗️참고) 가장 처음의 호출을 포함한 중첩 호출의 최대 개수를 '재귀 깊이'라고 한다.
function recursion () {
console.log("Chimmy is")
console.log("comeback!")
recursion()
}
// 자기 자신을 끝없이 호출, 같은 코드가 계속 실행된다.♻️ 단계별로 재귀 이해하기
❗️문제
자연수로 이루어진 리스트(배열)를 입력받고,
리스트의 합을 리턴하는 함수 arrSum 을 작성하시오.
1️⃣ 문제를 작게 쪼개기
arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5])
...2️⃣ 문제를 가장 작은 단위로 쪼개기
...
arrSum([3, 4, 5]) === 3 + arrSum([4, 5])
arrSum([4, 5]) === 4 + arrSum([5])
arrSum([5]) === 5 + arrSum([])3️⃣ 문제 해결하기
2번에서 도달한 가장 작은 문제는 arrSum([])이었다.
👉 빈 배열의 합은 0이므로, 0을 리턴해주면 된다.
위 단계를 반영한 arrSum함수
function arrSum(arr) {
// 빈 배열을 받았을 때 0을 리턴하는 조건문
// --> 가장 작은 문제를 해결하는 코드 & 재귀의 탈출 조건
if (arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
}
console.log(arrSum([1, 2, 3, 4, 5]));
// 15
//❗️참고) 재귀 깊이 => 5
//❗️참고) 재귀의 깊이가 커지면 많은 메모리를 차지하게 된다.❓언제 재귀를 사용하나요?
－ 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
－ 중첩된 반복문이 많거나 중첩 횟수를 예측하기 어려운 경우
－ 반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우
♻️ 일반적인 재귀 함수 템플릿
function recursive(input1, input2, ...) {
// base case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive case : 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
}♻️ 꼬리 재귀 함수
재귀함수의 콜 스택이 깊어질수록 메모리 스택 오버 플로우가
발생하는 문제를 해결하기 위한 재귀 호출 방식을 꼬리 재귀라고 한다.
즉, 꼬리 재귀는 재귀의 단점을 보완해주는 최적화 방법이라는 것.
❗️참고) 일반 재귀와 큰 차이점은, 반환값에서 추가 연산을 필요로 하지 않는다는 점이다.
▷ 일반적인 재귀 함수
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
console.log(factorial(3))
// 3 * (2 * factorial(1)
// 3 * (2 * 1)
// 3 * 2
// 결과값: 6
// 특징: 반환하면서 계산한다.▷ 꼬리 재귀 함수 - 방법 1
function facTail(n, acc = 1) {
if (n === 1) return acc;
return facTail(n - 1, n * acc);
}
console.log(facTail(3))
// 결과값: 6
// 특징: acc변수에 계산된 값을 저정한 후 한번에 반환한다.▷ 꼬리 재귀 함수 - 방법 2
function facTail(n, acc) {
if (n === 1) return acc;
return facTail(n - 1, n * acc);
}
console.log(facTail(3, 1));
// 결과값: 6♻️ 재귀 함수 간단한 예시 코드
▷ 팩토리얼 n!
function fac(n) {
if (n === 1) return 1;
return n * fac(n - 1);
}
console.log(fac(5));
// 5 x 4 x 3 x 2 x 1 = 120 출력▷ 피보나치 수열
Fn = ( Fn－1 ) + ( Fn－2 )
function fibonacci(num) {
if (num === 1 || num === 0) return num;
return fibonacci(num - 1) + fibonacci(num - 2);
}
console.log(fibonacci(5));
// 5▷ concat 사용1
// 수(num)와 배열을 입력받아 차례대로
// num개의 요소만 포함된 새로운 배열을 리턴해야 한다.
function take(num, arr) {
if (num === 0 || arr.length === 0) return [];
let result = arr[0];
return [result].concat(take(num - 1, arr.slice(1)));
}
console.log(take(2, [1, 2, 3, 4]));
// [ 1, 2 ]▷ concat 사용2
// 배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 한다.
function reverseArr(arr) {
if (arr.length === 0) return [];
let result = arr[0];
return reverseArr(arr.slice(1)).concat(result);
}
console.log(reverseArr([1, 2, 3]));
// [ 3, 2, 1 ]♻️ 재귀 함수 복잡한 예시 코드
▷ 객체
// 러시아 전통인형 마트료시카에 대한 정보를 담은 객체와
// 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 한다.
function findMatryoshka(matryoshka, size) {
if (matryoshka.size === size) {
return true;
} else if(matryoshka.matryoshka) {
return findMatryoshka(matryoshka.matryoshka, size);
}
return false;
}
const matryoshka = {
size: 10,
matryoshka: {
size: 9,
matryoshka: null,
},
};
console.log(findMatryoshka(matryoshka, 10));
// true▷ 배열1
// 선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아
// 조건에 맞는 선물이 있는지 여부를 리턴해야 한다.
function unpackGiftbox(giftBox, wish) {
if (giftBox.length === 0 || wish === "") return false;
for (let i = 0; i < giftBox.length; i++) {
if (giftBox[i] === wish) return true;
if (Array.isArray(giftBox[i])) {
if (unpackGiftbox(giftBox[i], wish) === true) return true;
}
}
return false;
}
const giftBox = ["macbook", "mugcup", ["eyephone", "postcard"], "money"];
console.log(unpackGiftbox(giftBox, "iphone"));
// false▷ 배열2
// 다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 한다.
function flattenArr(arr) {
if (arr.length === 0) return [];
let result = [];
for (let i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i])) {
let a = flattenArr(arr[i]);
result = [...result, ...a];
} else {
result.push(arr[i]);
}
}
return result;
}
console.log(flattenArr([[1], 2, [3, 4], 5]));
// [1, 2, 3, 4, 5]
🐾