재귀(1)

• 학습목표
  • 재귀가 무엇이고, 어떻게 유용한가?
  • 재귀 함수 작성의 두 가지 핵심 구성요소는?
  • call stack과 재귀함수
  • 재귀함수 디버깅
  • helper method recursion과 pure recursion의 비교
• 재귀함수를 사용하는 이유?
  • 자기자신을 호출하는 함수
  • 재귀함수는 모든곳에서 활용된다.
    • JSON.parse, JSON.stringify
    • document.getElementById, DOM 순회 알고리즘(DOM은 모든 요소가 중첩된 트리 구조로 되어있음)
    • 객체 순회
    • 반복대신 재귀를 쓰는것이 더 깔끔하다.
• call stack
  • 함수를 호출하면 콜스택의 꼭대기에 쌓인다.(push)
    자바스크립트가 함수안에 더이상 실행할 코드가 없다면, 컴파일러가 스택의 제일 위에 있는 항목부터 제거한다.(pop)
• 재귀함수에서 기본적인 두가지 값
  • Base Case : 재귀함수를 끝내는 종료 조건
  • Different Input : 다른 입력값
• 재귀함수 예시 1.

// 재귀함수로 구현
function countDown(num){
  //Base Case
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
countDown(3)

// 반복문으로 구현
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

• 재귀함수 예시 2.

function sumRange(num) {
  //Base Case
  if (num === 1) return 1;
  return num + sumRange(num - 1);
}
sumRange(3) //6
//1. return 3 + sumRange(2)
//2.              return 2 + sumRange(1)
//3.                             return 1 <Base Case>
//콜스택은 LIFO방식이라 거꾸로 호출됨 3 > 2 > 1 순서로 나감

• 팩토리얼 구현

//반복문으로 구현하기
function factorial(num){
    let total = 1;
    for(let i = num; i > 1; i--){
        total *= i
    }
    return total;
}
//재귀함수로 구현하기
function factorial(num){
  //Base Case
    if(num === 1) return 1;
    return num * factorial(num-1);
}

• 통상적인 재귀의 잠재적인 위험
  • Base Case가 없는 경우
  • 잘못된 값을 return, 애초에 return하는 것을 잊은 경우, 즉 return이 중요!!
  • Stack overflow! 즉 콜스택이 넘치는 에러, 재귀가 멈추지 않음
• helper method 재귀
  • 재귀적이지 않은 외부 함수가 재귀적인 내부 함수를 호출하는 패턴
  • 배열이나 데이터 목록 같은 것을 컴파일 해야할 때
    예를 들어 어느 배열에서 모든 홀수값을 수집하는 것..
    • 함수가 호출된 후에도 변수가 값을 유지해야 할때,
      단순 재귀함수를 쓰면 함수가 호출될 때마다 그 배열이 다시 리셋됨..즉 return할 result를 재귀함수 밖, 둘러싸는 함수에다가 선언

//외부함수를 호출해서 무언가를 내부로 전달할수 있다.
function outer(input){
    
    var outerScopedVariable = []

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

    return outerScopedVariable;
}

//배열에서 모든 홀수값을 수집
function collectOddValues(arr){
    
    let result = []

    function helper(helperInput){
        if(helperInput.length === 0) {
            return;
        }
        
        if(helperInput[0] % 2 !== 0){
            result.push(helperInput[0])
        }
        //더 작은 부분배열을 만들어서 helper로 전달하고, 다시 실헹
        helper(helperInput.slice(1))
    }
    
    helper(arr)

    return result;
}

collectOddValues([1,2,3,4,5])

• 순수 재귀
  • helper method 재귀없이 순수 재귀함수로 문제 풀이시 팁!
    • 배열을 사용하고, 헬퍼 메소드 없이 순수 재귀 솔루션을 작성하는 경우에는,
      • 배열을 복사하는 slice, spread연산자(operator),concat같은 메소드를 사용할수 있다. 그러면 배열을 변경할 필요가 없다.
        즉 일종의 결과를 축적할 수 있다.
      • 문자열은 immutable하기 때문에, slice나 substring을 사용해서 사본을 만들어야 한다.
      • 객체의 경우, Object.assign이나 spread연산자를 사용하는게 유용
  • 위에 helper method 재귀문제를 순수 재귀함수로 풀이했을 때

function collectOddValues(arr){
    let newArr = [];
    
    if(arr.length === 0) {
        return newArr;
    }
        
    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }
        //재귀힘수가 호출될때마다 newArr는 다시 초기화  
    newArr = newArr.concat(collectOddValues(arr.slice(1)));
    return newArr;
}

collectOddValues([1,2,3,4,5]) // [1,3,5]
//1.[1].concat(collectOddValues([2,3,4,5]))
//2.                [].concat(collectOddValues([3,4,5]))
//3.                                [3].concat(collectOddValues([4,5]))
//4.                                                  [].concat(collectOddValues([5]))
//5.                                                                   [5].concat(collectOddValues([]))
//6.                                                                                      []
//콜스택에서 꺼내지는건 6>5>4>3>2>1 

Array.prototype.slice(begin,end)

• slice() 메서드는 어떤 배열의 begin 부터 end 까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환. 원본 배열은 바뀌지 않는다.
• begin
  • optional, 0을 시작으로 하는 추출 시작점에 대한 인덱스를 의미
  • 음수 인덱스는 배열의 끝에서부터의 길이를 나타낸다.
    • slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출
• end
  • optional, 추출을 종료 할 0 기준 인덱스, end 인덱스를 제외하고 추출

const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];
animals.slice(1) // ["bison","camel", "duck", "elephant"]
animals.slice(2, 4) // ["camel", "duck"]
animals.slice(-2) // ["duck", "elephant"]
animals.slice(2, -1) // ["camel", "duck"]
animals.slice() // ["ant", "bison", "camel", "duck", "elephant"]

Array.prototype.concat()

• concat() 메서드는 인자로 주어진 배열이나 값들을 기존 배열에 합쳐서 새 배열을 반환, 원본 배열은 바뀌지 않는다.

const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2);
console.log(array3); //["a", "b", "c", "d", "e", "f"]