ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 재귀함수
    개발 2020. 4. 12. 16:16

    재귀함수란?

    함수가 자기 자신을 호출하는 행위를 가리켜 재귀 호출(recursive call) 이라고 합니다. 이러한 재귀 호출을 수행하는 함수를 재귀 함수 라고 합니다.

     

    재귀함수 예시로 유명한 팩토리얼 예제를 간단히 코드로 옮겨보겠습니다.

    function fact(n){
      if(n <= 1) return 1;
      return n * fact(n-1);
    }
    fact(5);  // 120

    이 예제는 5에 대한 팩토리얼을 구하는 예제입니다. fact함수 안에는 매개변수 n이 1보다 작거나 같으면 1을 return 하면서 이 재귀함수를 종료하는 조건을 넣어주었습니다. 종료조건이 충족하기 전까지는 매개변수 n 에 fact함수를 재귀호출하여 곱을 return 하고 있는데요, fact함수를 재귀호출 할 때는 전달인자로 n-1 을 전달해주고 있습니다. 

    따라서, 이 재귀함수의 출력 값은 5 *  4 * 3 * 2 * 1 이 되어 120이 될 것 입니다.

     

    재귀의 중요한 3가지 특성

    모든 재귀함수는 3가지의 특성을 갖습니다.

     

    1. 종료조건

    위의 예시에서 if의 조건문 처럼 if( 이 조건에 맞는 값이 들어온다면 ) { 종료 }; 와 같이 종료 조건이 들어갑니다. 이 종료 조건은 재귀의 안전장치라고 볼 수 있습니다. 조건에 맞지 않는 값이 들어왔을 때, 재귀가 계속하여 동작하는 것을 방지해줍니다. 

    위의 예제에서 if( n <= 1) { return 1; } 은 fact함수의 종료 조건 입니다. 그래서 우리는 0 이하의 값이 들어 왔을 때, 이 함수가 작동하지 않길 원합니다.

    만약, 이 종료조건이 없이 계속해서 재귀 호출을 하게 된다면 계속해서 자기 자신을 호출하므로 무한루프에 빠져 결국엔 아래와 같은 콜스택 오버 에러가 뜰 것 입니다. 

    Uncaught RangeError: Maximum call stack size exceeded

     

    2. 기반조건

    1번의 예시에 있는 조건문이 종료 조건을 위한 것이였다면 이 기반 조건은 간단하게 if( 이 조건에 맞는 값이 들어온다면) { 실행 }; 과 같이 볼 수 있습니다. 이 조건 역시 재귀 함수를 멈춘다는 점을 감안하면, 기반 조건 또한 어쩌면 재귀의 종료조건과 비슷합니다.

    종료조건은 조건에 맞지 않는 값을 잡아내는 조건문이라면 이 기반조건은 현재 실행하고 있는 재귀 함수의 목적입니다. 

    위의 예제에서의 기반조건은 if( n <= 1) { return 1; } 이 종료 조건이면서 기반 조건입니다. 왜냐하면 n 이 0 이하의 값이 된다면 팩토리얼을 구하는데 성공한 것이라고 볼 수 있기 때문입니다.

     

    3. 재귀

    재귀란 함수가 자기 자신을 호출하는 것 이라고 배웠습니다. 위의 팩토리얼 예제에서 return n * fact( n - 1 ); 이 부분이 실제로 재귀가 일어나는 곳입니다. fact()함수는 매개변수로 들어온 값 n이 fact( n -1 ) 함수의 결과 값으로 곱해진 어떠한 값을 반환합니다.

    즉, n값으로는 fact함수를 호출하면서 전달인자로 넣어준 5 이고, fact( n - 1)은 5 - 1, 4 - 1 ... 이렇게 계속해서 5 *  4 * 3 * 2 * 1 이 되어 재귀호출을 진행할 것입니다

     

    재귀함수를 반복문으로 표현해보기

     

    위의 예제에서 보면 재귀호출 또한 반복문처럼 조건문이 있고 조건에 충족할 때 까지 반복적으로 재귀호출을 해주기 때문에 아래 예제와 같이 반복문으로 표현할 수도 있습니다.

    function fact(n) {
      let result = 1;
      for (let i = n; i > 0; i--) {
        result = result * i;
      }
      return result;
    }
    fact(5)  // 120

     

    마지막으로 정리하면서 재귀함수의 장점과 단점을 살펴 보자면 다음과 같이 설명할 수 있겠습니다.

    장점 : 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 사용하면 좋고, 가독성을 높혀주기도 합니다.

    단점 : 메모리를 많이 차지하며 성능이 반복문에 비해 느립니다. 함수를 호출 시 함수의 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치가 스택 메모리에 저장됩니다. 따라서, 재귀함수를 쓰게되면 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있습니다.

    '개발' 카테고리의 다른 글

    prototype과 prototype Chain  (0) 2020.04.14
    생성자와 new  (0) 2020.04.12
    객체지향 프로그래밍  (0) 2020.04.12
    클로저에 대해서  (0) 2020.04.01
    스코프에 대해서  (2) 2020.03.31
Designed by Tistory.