재귀(Recursion)

 

---

1. 스토리 타임 : 마틴과 드래곤

슬라이드

Recursion Slides

---

2. 재귀 함수를 사용하는 이유

재귀란?

-> 자기 자신을 호출하는 과정(함수)

 

재귀가 왜 필요한가?

-> 모든 곳에 존재하기 때문이다!

• JSON.parse / JSON.stringify
• document.getElementById & DOM traversal algorithms
• 객체 순회 (Object traversal)
• 더 복잡한 알고리즘에 사용
• 반복문 보다 더 깔끔한 대체제로 사용

 

재귀 함수가 어떻게 동작하는가?

종료조건(base case)을 만날 때까지

다른 입력값으로 동일한 함수를 호출한다.

 

종료조건(Base Case)란?

재귀가 끝나는 조건을 말한다.

기본 케이스가 재귀를 이해하는데 가장 중요한 개념이다.

 

재귀 함수의 두 가지 중요한 부분

• 종료조건 (Base Case)
• 다른 입력값 (Different Input)

 

 

 

3. 스택 호출하기

Chorme dev tool 에서 wakeUp함수에 breakpoint를 걸고 하나씩 호출해본다.

callstack에 함수가 쌓이고 사라지는 과정을 확인하면서 스택을 이해한다.

재귀함수는 스택에 다른 입력값으로 동일한 함수가 계속 쌓인다.

그리고 어느 조건에 따라 종료조건을 만나면 callstack에서 함수가 하나씩 사라지면서 프로그램이 종료된다.

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()

 

 

4. 첫번째 재귀 함수

// 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!")
}

재귀함수의 콜스택

 

5. 두번째 재귀 함수

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

sumRange(4)

 

6. 반복문으로 팩토리얼 구현하기

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

7. 재귀 호출로 팩토리얼 구현하기

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

 

 

8. 통상적인 재귀의 잠재적 위험

1. 종료 조건이 없을 때
2. 값을 반환하는 것을 잊을 때
3. 잘못된 값을 반환할 때
-> stack overflow (스택초과)가 발생한다.

 

 

9. Helper 메소드 재귀

헬퍼 메소드 재귀는
재귀적이지 않은 외부 함수가
재귀적인 내부 함수(inner function)를 호출하는 패턴이다.

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])

 

 

10. 순수 재귀

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])

CALLSTACK

호출
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( [ ] ) )
                        		↘return [ ]

반환
collectOddValues( [1, 2, 3, 4, 5] )   	=> [ 1, 3, 5]
[1].concat( collectOddValues( [2, 3, 4, 5] ) )    => [ 1, 3, 5] ↖
	[ ].concat( collectOddValues( [3, 4, 5] ) )   => [ 3, 5 ] ↖
		[3].concat( collectOddValues( [4, 5] ) )   => [ 3, 5 ] ↖
			[ ].concat( collectOddValues( [5] ) )   => [ 5 ] ↖
				[5].concat( collectOddValues( [ ] ) )  => [ ] ↖
					return [ ]	→ → → → → → → → →  ↑

Pure Recursion Tips

• 배열을 복제하지 않고 복사하기 위해서 slice, concat 메서드나 spread operator를 사용하라.
• 문자열은 불변성이 있다. 그래서 문자열을 복사하기위해 slice, substr, substring 같은 메서드를 사용하라.
• 객체를 복사하기 위해서 Object.assign이나 spread operator를 사용하라.

What about big O?

• 시간 복잡도 측정은 비교적 간단하다. 재귀 함수의 시간 복잡도를 입력값에 대해 수행해야 하는 재귀 호출의 수로 측정할 수 있다.
• 공간 복잡도을 측정하는 것은 조금 더 어렵다. 호출 스택에는 메모리가 필요하므로 재귀 함수의 공간 복잡도를 지정된 시간에 호출 스택의 최대 함수 수로 측정할 수 있다.