7월 31(토) 재귀함수

재귀함수

어떠한 문제를 해결 할때, 동일한 구조의 더 작은 문제를 함으로써 주어진 문제를 해결하는 방법

재귀호출 => 실행 과정 중 자기 자신을 호출 한다.

재귀사용에 적합한 예

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문에 많거나 중첩 횟수(number of loops)를 예측하기 어려운 경우

모든 재귀 함수는 반복문으로 표현 할 수 있다.

재귀적 사고하기

1. 재귀 함수의 입력값과 출렵값 정의 하기
   =>문제를 가장 추상적으로 또는 가장 단순하게 정의 하는 것
2. 문제를 쪼개고 경우의 수를 나누기
   =>주어진 문제를 어떻게 쪼갤지 고민한다
   => 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분 할 수있는지 확인 한다.
   => 일반적인 경우 입력 값으로 기준을 정한다.
   => 중요 관점 "입력값이나 문제의 순서와 크기"
   (1.입력값, 2.문제 상황을 크기로 구분, 3.순서를 명확하게 정한다.)
3. 단순한 무제 해결하기
   =>문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결 한다.
   =>재귀의 기초(base Case)
   =>base Case는 재귀 함수를 구현 할 때, 재귀의 탈출 조건 (재귀의 호출이 멈추는 조건)을 구성한다.
4. 복잡한 문제 해결하기
   =>길이가 1이상인 배열의 함수에 입력된 경우
   =>맨 앞의 요소에 대한 결과 값을 따로 구하고(head)
   =>나머지요소를 새로운 입력 값으로 갖는 문제로 구분, 이를 해결하여 얻은 결과를 head에 더 한다.
   =>배열일 경우 head, tail로 나워서 생각한다.

추가적으로 알아둘 것

객체 구조분해 할당(MDN)

let o = {p: 42, Q: true}
let {p: foo, q: bar} = o
console.log(foo); // 42
console.log(bar); // true

배열 구조분해 할당(MDN)

let foo= ["ond", "two", "three"]
let [red, yellow, green] = foo;
console.log(red); // "one"
console.log(yellow); // "two"
console.log(green); // "three"

배열 구조분해 할당(spread)

let a = [1, 2, 3, 4, 5]
let [head, ...tail] = a
console.log(head); // 1 // number
console.log(tail); // [2, 3, 4, 5] // array(배열)

메소드

includes()
=>배열안에 해당하는 요소가 있는지 확인
=>있으면 true, 없으면 false로 반환

재귀 함수 템플릿

function recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
    if(문제를 더 이상 쪼갤 수 없을 경우) {
        return 단순한 문제의 해답
    }
    //recursive Case
    //그렇지 않은 경우
    return 더 작은 문제로 새롭게 정의된 문제
    // 예1. someValue + recursive(input1Changed, input2Changed, ...)
    // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}