재귀(Recursion)

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

 

재귀는 자기 자신을 호출하는 함수. 

* 중단점(종료점) 반드시 있어야 함!

* 스택 오버플로는 재귀가 멈추지 않는다는 의미. 종료점이 없을 때.

# 재귀 함수 예제 1

// Recursive Version
function countDown(num){
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
countDown(3)

// Iterative Version
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

# 재귀 함수 예제 2

function sumRange(num){
   if(num === 1) return 1; 
   return num + sumRange(num-1);
}

sumRange(4)

# 재귀 함수 예제 3

// Recursive Version
function factorial(num) {
    if(num ===1 ) return 1;
    return num * factorial(num - 1);
}

// Iterative Version
function factorial(num) {
    let total = 1;
    for(let i = num; i > 1; i--){
        total *= i;
    }
    return total;
}

---

# 헬퍼 메소드 재귀

: 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴

function outer(input){
    
    var outerScopedVariable = []

    function helper(helperInput){
        // modify the outerScopedVariable
        helper(helperInput--)
    }
    
    helper(input)

    return outerScopedVariable;

}

# 헬퍼 메소드 재귀 EXAMPLE

Let's try to collect all of the odd values in an array

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;

}

---

#순수 재귀

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;
}

Pure Recursion Tips

• For arrays, use methods like slice, the spread operator, and concat that make copies of arrays so you do not mutate them
• Remember that strings are immutable so you will need to use methods like slice, substr, or substring to make copies of strings
• To make copies of objects use Object.assign, or the spread operator