재귀함수 Recursion

Recursion

---

• 자기 자신을 호출하는 함수

function foo () {
   foo();
}

// 무한 반복으로 콜스텍 오버 에러를 낸다. 
// 반드시 탈출 조건을 만들어 주어야 한다.

• 재귀 함수를 사용할 때 탈출 조건을 꼭 만들어 주어야 한다.그렇지 않으면 무한 루프를 돌다가 결국 콜스텍 오버 에러를 낸다.

• 트리구조를 표현, 탐색하기에 재귀함수가 유용하다

• 장점: 알고리즘이 재귀로 표현했을 때 가독성이 좋다 .
• 단점: 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용한다.

Factorial

---

자기 자신의 수에 -1 작은 수를 곱하는 것을 반복해서 1이 될 때까지 곱하는 것.

5! = 5 * 4 * 3 * 2 * 1 = 120  === ( 5 * 4! )

4! = 4 * 3 * 2 * 1 = 24 === ( 4 * 3!)

3! = 3 * 2 * 1 = 6 === ( 3 * 2!)

2! = 2 * 1 = 2 === ( 2 * 1!)

1! = 1 =1 

 5 * 4!
 4 * 3!
 3 * 2!
 2 * 1!
 
 n! = n * (n-1)!

재귀 함수 표현

function factorial (n) {
   if(n === 1){ 
       return 1;
   } // 탈출조건이 된다
   
   return n * factorial(n-1);
}

반복문 표현

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

Fibonacci 수열

---

앞의 두수의 합이 다음번 수열의 값.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

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

n > 1

fib(0) === 0
fib(1) === 1

재귀 함수 표현

function fibonacci (n) {
  // n === (n - 1) + (n - 2)
  if(n === 0){
    return 0;
  }
  if(n === 1){
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
 }

재귀 함수 예제

---

ex1) 모든 DOM 요소 tagName console.log 찍기

function logAll (el) {
  // TO DO..
}

logAll(document.body);

문제 풀이

function logAll (el) {
   console.log(el.tagName);

   if(el.children.length > 0) {
      for(var i = 0; i < el.children.length; i++) {
         logAll(el.children[i]);
      }
   }
}

logAll(document.body);

ex2) getElementsByClassName 재귀 함수

function getElementsByClassName (el) {
  // TODO..
}

문제풀이

function getElementsByClassName (className) {
   let arr = [];
   let body = document.body;

   function recursion(el) { 
      if(el.classList.contains(className)){
         arr.push(el);
      }
      if(el.children.length > 0){
         for(let i =0; i < el.children.length; i++){
             recursion(el.children[i]);
         }
      }
   }
 
   recursion(body);
   
   return arr;
 }

getElementsByClassName(className);