순환 (Recursion)

# 개념

• 순환 또는 재귀함수.
• Recursive 메서드는 자기 자신을 호출한다.
• Resursive 메서드는 Base Case와 Recursive Case를 가져야 한다.

-Base Case : Recursion을 벗어나는 경우

-Recursive Case : 자기 자신을 호출하는 경우. 최종적으로 Base Case로 수렴해야 한다.

---

# 예제

n까지의 합계 구하기

const sum = n => {
    if (n <= 0) return 0;
    else return n + sum(n-1);
}

---

Factorial: n! 구하기

const factorial = n => {
    if(n == 0) return 1;
    else return n * factorial(n-1);
}

---

피보나치 수 구하기

const fibonacci = n => {
    if(n < 2) return n;
    else return fibonacci(n-1) + fibonacci(n-2);
}

---

최대공약수(GDC), 최소공배수(LCM) 구하기

// GCD
const gcd = (a, b) => {
    if(b === 0) return b;
    else return gcd(b, a%b);
}

// LCM
const lcm = (a, b) => {
    return a*b / gcd(a, b);
}

---

멱집합 구하기

const data = ['a','b','c','d','e'];
const len = data.length;
const include = new Array[len].fill(false);

const powerSet = k => {
    if(k === len){ // 리프 노드라면
    	data.forEach((v, i) => {
            if(include[i]) console.log(v);
        });
        return;
    }
    include[k] = false;
    powerSet(k+1); // 왼쪽 노드 탐색
    include[k] = true;
    powerSet(k+1); // 오른쪽 노드 탐색
}