📖 재귀는 왜 사용할까?
재귀는 자기 자신을 호출하는 절차다. 재귀 함수는 자기 자신을 호출한다.
그렇다면 재귀를 왜 알아야할까? 재귀는 어디서나 자주 사용되기 때문이다.
- JSON.parse / JSON.stringify -> 항상은 아니지만 재귀 방식을 택해서 작성할 때 많다
- document.getElementById 와 DOM 순회 알고리즘 -> DOM은 모든 요소가 중첩된 트리 구조기 때문이다. 중첩 구조를 탐색 시 재귀를 쓸 수 있다.
- 객체 순회 알고리즘
이 외의 복잡한 자료구조를 탐색시에도 재귀를 사용할 수 있다.
📖 콜스택(Call Stack)
우리는 오류없이 재귀 함수를 호출하기 위해, 동작에 대해 이해할 필요가 있다.
거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다. 함수는 무작위로 실행되는게 아니라 순서대로 실행되는데, 이 순서를 관리하는 데이터 구조가 콜스택이다.
콜스택은 말 그대로 stack 자료구조를 사용한다. 함수를 호출하면, 호출 스택의 맨 위에 쌓인다. 만약 더이상 실행할 것이 없으면, 컴파일러는 스택의 제일 위의 항목을 제거한다.
function takeShower(){
return "Showering!"
}
function eatBreakfast(){
let meal = cookFood()
return `Eating ${meal}`
}
function cookFood(){
let items = ["Oatmeal", "Eggs", "Protein Shake"]
return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
takeShower()
eatBreakfast()
console.log("Ok ready to go to work!")
}
wakeUp()위 코드가 실행되면, 콜스택에는 다음과 같이 스택이 쌓일 것이다.
재귀 함수는 콜스택에 동일한 함수를 콜스택에 계속 추가한다. 그리고 호출시에는 스택에서 pop()되는데, 이 과정이 어떤 시점에는 종료되어야 한다.(이때 조건을 주어 종료시킨다.)
📖 재귀함수
재귀함수에서 필수적인 두 가지 부분이 있다.
1. Base Case
재귀가 멈추는 조건이다. 재귀에도 끝이 있어야 오류가 발생하지 않는다.
2. 다른 입력값
같은 함수를 계속해서 호출하겠지만, 다른 입력값으로 함수를 호출해야 한다.
📌 Recursive Function 1
// Recursive Version
function countDown(num){
if(num <= 0) {
console.log("All done!");
return;
}
console.log(num);
num--;
countDown(num);
}
countDown(3);
//print 3
//countDown(2);
//print 2
//countDown(1);
//print 1
//countDown(0);
//All done!
// Iterative Version
function countDown(num){
for(var i = num; i > 0; i--){
console.log(i);
}
console.log("All done!");
}
📌 Recursive Function 2
function sumRange(num){
if(num === 1) return 1;
return num + sumRange(num-1);
}
sumRange(4);
//4+sumRange(3);
//4+3+sumRange(2);
//4+3+2+sumRange(1);
//4+3+2+1
📌 Recursive Function 3
//iterative 버전
function factorial(num){
let total = 1;
for(let i = num; i > 1; i--){
total *= i
}
return total;
}
//recursive 버전
function factorial(num){
if(num === 1) return 1;
return num * factorial(num-1);
}
factorial(3);
//3*factorial(2)
//3*2*factorial(1)
//3*2*1📌 재귀함수 작성 시 발생 가능한 잠재적 문제점
- 종료 조건이 없는 경우 -> 최대 스택 크기 초과 에러(stack overflow) 발생가능
- 잘못된 값을 반환하거나 반환하는 것을 잊는 경우
function factorial(num){
if(num === 1) return 1;
return num * factorial(num); //종료 조건에 다다를 수 없게됨
}
function factorial(num){
if(num === 1) console.log(1); //반환하는 것을 잊는 경우
return num * factorial(num-1);
}📌 Helper Method Recursion
//어떤 배열에서 모든 홀수값을 수집하는 함수
function collectOddValues(arr){
//빈배열
let result = [];
//내부함수(헬퍼 함수)
//함수가 호출될때마다 빈배열로 리셋되는 문제를 막음
function helper(helperInput){
//길이가 0이면 종료
if(helperInput.length === 0) {
return;
}
//홀수냐
if(helperInput[0] % 2 !== 0){
result.push(helperInput[0])
}
//맨 앞 한자리 자름
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
collectOddValues([1,2,3,4,5,6,7,8,9]);📌 Pure Method Recursion
//순수 재귀를 이용한 솔루션
function collectOddValues(arr){
//빈 배열 newArr를 이용
let newArr = [];
//배열 길이가 0이면 종료
if(arr.length === 0) {
return newArr;
}
//홀수라면 인덱스 0의 값을 push()
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
//배열의 0번째 인덱스를 잘라낸 값을 인수로 받아 재귀적 호출
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1,2,3,4,5]);
- 배열 사용시 slice, spread, concat같은 얕은 복사를 통해 배열을 사용한다.
- 문자열은 불변성을 가지므로 slice, substr, substring을 사용해서 사본을 만들어야 한다.
- 객체의 경우 Object.assign이나 spread 연산자를 사용하는 것이 유용하다.
✏️ Power
power
Write a function called power which accepts a base and an exponent. The function should return the power of the base to the exponent. This function should mimic the functionality of Math.pow() - do not worry about negative bases and exponents.
function power(base, exp) {
if (exp === 0) {
return 1;
}
return base * power(base, exp - 1);
}✏️ Factorial
factorial
Write a function factorial which accepts a number and returns the factorial of that number. A factorial is the product of an integer and all the integers below it; e.g., factorial four ( 4! ) is equal to 24, because 4 3 2 * 1 equals 24. factorial zero (0!) is always 1.
function factorial(num){
if(num === 0){
return 1;
}
return num*factorial(num-1);
}✏️ ProductOfArray
productOfArray
Write a function called productOfArray which takes in an array of numbers and returns the product of them all.
function productOfArray(arr){
if(arr.length === 0){
return 1;
}
return arr[0]*productOfArray(arr.slice(1));
}✏️ RecursiveRange
recursiveRange
Write a function called recursiveRange which accepts a number and adds up all the numbers from 0 to the number passed to the function
function recursiveRange(num){
if(num === 0){
return 0;
}
return num+recursiveRange(num-1);
}
✏️ Fibonacci sequence
fib
Write a recursive function called fib which accepts a number and returns the nth number in the Fibonacci sequence. Recall that the Fibonacci sequence is the sequence of whole numbers 1, 1, 2, 3, 5, 8, ... which starts with 1 and 1, and where every number thereafter is equal to the sum of the previous two numbers.
function fib(num){
if(num<=2){
return 1;
}
return fib(num-1)+fib(num-2);
}💗 Power Solution
function power(base, exponent){
if(exponent === 0) return 1;
return base * power(base,exponent-1);
}💗 Factorial Solution
function factorial(x){
if (x < 0 ) return 0; //0미만인 값 처리
if (x <= 1 ) return 1;
return x * factorial(x-1);
}💗 ProductOfArray Solution
function productOfArray(arr) {
if(arr.length === 0) {
return 1;
}
return arr[0] * productOfArray(arr.slice(1));
}💗 RecursiveRange Solution
function recursiveRange(x){
if (x === 0 ) return 0;
return x + recursiveRange(x-1);
}
💗 Fibonacci sequence Solution
function fib(n){
if (n <= 2) return 1; //2이하라면 n-2가 음수값이되므로 그 전에 리턴
return fib(n-1) + fib(n-2);
}✏️ Reverse
reverse
Write a recursive function called reverse which accepts a string and returns a new string in reverse.
function reverse(str){
if(str.length === 0){
return "";
}
return reverse(str.slice(1)) + str[0];
}✏️ isPalindrome
isPalindrome
Write a recursive function called isPalindrome which returns true if the string passed to it is a palindrome (reads the same forward and backward). Otherwise it returns false.
function isPalindrome(str){
if(str.length<=1){
return true;
}
if(str.length === 2){
return str[0] === str[1];
}
if(str[0] === str.slice(-1)){
return isPalindrome(str.slice(1,-1));
}
return false;
}✏️ someRecursive
someRecursive
Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.
function someRecursive(array, callback){
if(array.length === 0){
return false;
}
if(callback(array[0])){
return true;
}
return someRecursive(array.slice(1), callback);
}✏️ flatten
flatten
Write a recursive function called flatten which accepts an array of arrays and returns a new array with all values flattened.
function flatten(arr){
const result = []
arr.forEach((i) => {
if (Array.isArray(i)) {
result.push(...flatten(i));
} else {
result.push(i);
}
})
return result;
}위 코드는 mdn에 있는 내용이라 쉬웠다.
💗 Reverse Solution
function reverse(str){
if(str.length <= 1) return str; //이부분이 다르다 1보다 작거나 같을때 그냥 str 리턴해줘버림
return reverse(str.slice(1)) + str[0];
}💗 isPalindrome Solution
function isPalindrome(str){
if(str.length === 1) return true; //이부분에서 나는 <=1로 처리했는데 1이랑 같을때로만해도 될듯
if(str.length === 2) return str[0] === str[1];
if(str[0] === str.slice(-1)) return isPalindrome(str.slice(1,-1))
return false;
}💗 someRecursive Solution
function someRecursive(array, callback) {
if (array.length === 0) return false;
if (callback(array[0])) return true;
return someRecursive(array.slice(1),callback);
}💗 flatten Solution
function flatten(oldArr){
var newArr = []
for(var i = 0; i < oldArr.length; i++){
//요소가 배열이면 flatten수행해서 다시 펴준다
if(Array.isArray(oldArr[i])){
newArr = newArr.concat(flatten(oldArr[i])) //이부분에서 다름
} else {
newArr.push(oldArr[i])
}
}
return newArr;
}