[JSアルゴリズム]再帰(Recursion)

再帰関数を使用する理由

呼び出しスタック

    function takeShower() {
        return "샤워하자"
    }
    
    function eatBreakfast() {
        let meal = cookFood()
        return `${meal}를 먹자`
    }
    
    function cookFood() {
        let items = ['김치찌개', '미역국', '된장찌개']
        return items[Math.floor(Math.random()*items.length)];
    }
    
    function wakeUp() {
        console.log(takeShower());
        console.log(eatBreakfast());
        console.log("이제 출근하자")
    }
    
    wakeUp();

再帰関数に必要な2つの部分

function countDown(num) {
    if(num <= 0) {   // 1. Base Case
        console.log("All done!");
        return;  
    }
    console.log(num);
    num--;  // 2. 매번 다른 값 입력
    countDown(num);
}

countDown(5);

// 재귀를 이용한 sum 함수
function sumRange(num) {
    if(num === 1) return 1; // Base Case
    return num + sumRange(num-1); // 다른 input
}

sumRange(3) // 6

// return 3 + sumRange(2);
           // return 2 + sumRange(1);
                        // return 1;

// 재귀를 이용한 팩토리얼 함수
function factorial(num) {
    if(num===1) return 1; // Base Case
    return num * factorial(num-1); // 다른 input
}

factorial(4)

鬼を間違えた。

再帰的な2つの設計モード

1.Helperメソッドのリスニング

    function collectOddValues(arr){
        
        let result = [] // 데이터를 저장한 빈 배열, 이 빈 배열을 재귀함수 안에 정의하면 재귀호출시마다 초기화되는 문제가 있으므로, 재귀함수 밖에 정의한다.
    
        function helper(helperInput){
            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])

2.ピュア回帰

    function collectOddValues(arr){
        let newArr = [];
        
        if(arr.length === 0) {
            return newArr;
        }
            
        if(arr[0] % 2 !== 0){
            newArr.push(arr[0]);
        }
            
        newArr = newArr.concat(collectOddValues(arr.slice(1)));
        return newArr;
    }
    
    collectOddValues([1,2,3,4,5]);
    // [1].concat(collectOddValues([2,3,4,5]))
    								// [].concat(collectOddValues([3,4,5]))
    																// [3].concat(collectOddValues([4,5]))
    																								// [].concat(collectOddValues([5]))
    																															// [5].concat(collectOddValues([]))
    																																				// []
    
    // [1].concat([3].concat[5])
    // [1,3,5]