JavaScript - 재귀함수

정의: 어떤 함수가 스스로를 호출하는 것

재귀의 장점과 단점

• 장점
  • 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋음.
    -단점
  • 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용함.

---

재귀함수 예시 - Factorial

function Fac(n) {
  if(n === 1) return 1
}
  return n * fac(n-1) 

n=5일 때

n	n!
0	1
1	1
2	2*1 = 2
3	3*2*1 = 6
4	4*3*2*1 = 24
5	5*4*3*2*1 = 120

---

---

재귀함수의 특징

1. 재귀는 반복할 구문을 함수 단위로 분리해, 특정 조건이 만족할 때까지 실행하는 패턴으로 볼 수 있다.

   n!=n*(n-1)!
   n이 2가 될때까지 위 구문을 반복. (2!=2니까)

---

2. 기본적으로 반복문이므로, 모든 재귀는 반복문으로 표현할 수도 있다.

//재귀
function factorial(n) {
  if (n === 0) {
    return 1;
  } return n * factorial(n - 1);
}

//반복
function factorial(n) {
  let result = 1;
  for (let i = n; i > 0; i--) {
    result = result * i;
  }
  return result;
}

---

3. 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야 한다.

function factorial(n) {
  // Base Case
  // n이 0이면 재귀를 더 이상 진행하지 않는다
  if ( n === 0) {
    return 1;
  }
  
  // Recursive(재귀) Case 
  return n * factorial(n -1)
}

---

case 1:fibonacci 수열
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ...]

        fib(n) === fib(n-1) + fib(n-2)

                    n > 1
                 fib(0) === 0
                 fib(1) === 1)

---

case 2: tree 구조 탐색

• DOM Tree
• JSON