재귀함수

  • 함수를 스스로 호출하는 것
  • Programming Concept
  • 재귀를 작성할때는 무한루프를 돌지않게 탈출조건을 만들어야함.
function foo() {
  foo()
}

image.png
< Uncaught RangeError: Maximum call stack size exceeded >
: call stack에 더이상 담을 수가 없다는 에러

▼ call stack
어떤 함수가 호출되면, 실행 컨텍스트 execution context가 만들어진다.

  • call stack에 push
  • 함수를 벗어나면 call stack에서 pop
  • 함수 실행시 callstack이 해소되는 과정
    : 자바스크립트는 함수를 스택 위에 올리고 함수가 실행되고 끝이 나면 pop하여 없애는 것을 확인할 수 있었다.

image.png

! 아래의 예시 문제가 아무리 강의를 돌려봐도 이해가 가지 않아
help desk에 문의도 해보고 구글링도 해본 결과 좋은 글을 남겨주신 덕분에
문제를 이해할 수 있게되었다. !

  1. 팩토리얼 함수
function factorial(n) {
  if (n === 0) {
    return 1;
  }

  return n * factorial(n-1);
}
factorial(2)
/*
1. factorial(3) = 3 * factorial(2)
  1-1) factorial(2) = 2 * factorial(1)
  1-1-1) factorial(1) = 1 * factorial(0)
  1-1-1-1) factorial(0) = 1

  * 위의 과정을 거쳐서 아래와 같은 결과가 나온다.
  3 * 2 * 1 * 1 = 6
*/
  1. fibonacci 수열
function fibonacci(n) {
    if (n < 2)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

/*
1. fibonacci(4) + fibonacci(3)
  1) fibonacci(4) = fibonacci(3) + fibonacci(2)
    1-1) fibonacci(3) = fibonacci(2) + fibonacci(1)
                      = fibonacci(2) + 1     
                      = 1 + 1
      1-1-1) fibonacci(2) = fibonacci(1) + fibonacci(0)
                          = 1 + 0
    1-2) fibonacci(2) = 1

  1의 결과 fibonacci(4) = 2 + 1 = 3

  2) fibonacci(3) = fibonacci(2) + fibonacci(1)
                  = 1 + 1 = 2

  2의 결과 = 2

  1 + 2의 합은 5
  */

1) 팩토리얼 함수 참고 링크
https://www.everdevel.com/JavaScript/recursive-function.php
2) 피보나치 수열 참고 링크
https://www.codeit.kr/questions/1446
https://homoefficio.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion/

< for문을 재귀로 표현할 수도 있음 >

for(let i=0; i<3; i++) {
  console.log('hi)
}

function printHello(count) {
  if(count === 0) {
    return;
  }
  console.log('hi');
  debugger; 
  printHello(count - 1)
}

printHello(3)
  1. tree 구조 탐색
  • JSON : JavaScript Object Notation
    재귀는 트리구조, 탐색기를 다룰때 유용하게 쓰임
  • DOM
    DOM 탐색에도 유용함.
  1. 재귀의 장, 단점
  • 장점 : 알고리즘이 재귀로 표현하기에 자연스러울 경우, 프로그램의 가독성이 좋다.
  • 단점 : 값이 리턴되기 전까지 호출마다 call stack을 새로 생성하므로, 메모리를 많이 사용한다.
  • 재귀의 단점을 보안하는 방법
    https://jsbin.com/nihisaq/5/edit?html,js,output

! recursion과제 슈도코드로 팁 알려주셨다, 참고해서 과제 고고 !

  function getElementByClassName(calssName ) {
    let fount = [];
    let rootElement = document.body;

    function recursion(className, parentElement) {
      // parentElement의 자식 엘리먼트 중에 className이 있느냐?
      for() {
        if() {
          // 있으면, 해당 엘리먼트를  found에 넣는다
        } else {
          // 없으면, 해당 엘리먼트의 자식들까지(children) 다 찾는다
          // 예시) recurtion(className, parentElement[0])
        }
      }
    }
    recursion(className, parentElement);
  }