🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
재귀적으로 생각하기
📍 재귀 함수를 만들 때는 해당 함수가 이미 구현되었다고 생각하면 좋음!
ex) 5! = 5 * factorial(4);
1~5까지 배열의 합 = 5 + 1~4까지의 배열 합
📍 패턴 1: 단순 반복 실행
👉🏻 반복문으로 구현했을 때보다 큰 이점이 되는 부분이 없음
👉🏻 오히려 콜 스택 공간을 많이 차지해 성능이 for문보다 좋지 않음
📍 패턴 2: 하위 문제의 결과를 기반으로 현재 문제 계산
👉🏻 ex: facorial
//상위 문제 // 하위 문제
return number * factorial(number - 1);
👉🏻 for문을 이용해 계산하는 방식을 상향식 계산, 재귀를 이용하여 하위 문제 기반으로 현재 문제 계산하는 방식을 하향식 계산이라고 함
👉🏻 재귀를 사용한다고 모두 하향식 계산이 아니라 '하위 문제의 결과를 기반으로 현재 문제를 계산'할 때 하향식 계산이라고 함
👉🏻 상향식 계산은 for문, 재귀 함수로 모두 구현 가능하나 하향식 계산은 재귀 함수로만 구현 가능함
👉🏻 ex: 1~5까지의 배열의 합을 구하라
[1, 2, 3, 4, 5]
1~4까지 더하는 하위 문제
하위 문제에 5만 더하면 됨
[ sum_of_array.mjs ]
function sumArray(arr) {
if(arr.length == 1) return arr[0]; // 기저 조건
return sumArray(arr.slice(0, -1)) + arr[arr.length - 1];
}
let arr = [1, 2, 3, 4, 5];
let sum = sumArray(arr);
console.log(sum);
📍 (재귀를 하향식으로 사용 예시) 문자열의 길이 구하기
[ length_of_str.mjs ]
function strLength(arr) {
// 문자열의 길이 구하기를 재귀적으로 하향 방식으로 푼다면?
// 하위 문제: 구하려는 문자열의 마지막 원소를 제외한 나머지 부분
// + 나머지 문자열 하나를 더해 주기!
// 기저 조건: 배열에 원소가 없을 때
if(arr[0] == null) return 0;
return strLength(arr.slice(0, -1)) + 1;
}
let str = "abcde";
let len = strLength(str);
console.log(len);
📍 (재귀를 하향식으로 사용 예시) 지수함수 구하기
👉🏻 지수함수란? 숫자를 몇 제곱 하는 것
👉🏻 ex) 밑이 2이고, 지수가 5라면 2를 5번 곱하라는 뜻 ( 2 * 2 * 2 * 2 * 2)
[ power.mjs ]
function power(x, n) {
// 2의 5승을 구하는 게 문제라면?
// 하위 문제: 2의 4승 구하기
// + 2를 한 번 더 곱해 주면 끝!
if(n == 0) return 1; // 기저 조건
return power(x, n-1) * x; // 하위 문제
}
console.log(power(2, 5));