[알고리즘&자료구조] 재귀, Recursion

재귀란?

자신의 함수에서 자기자신을 호출하는 것

---

재귀함수를 사용하는 이유

모든 곳에서 재귀함수를 사용하고 있다.

예로 간략한 리스트는 다음과 같다.

- JSON.parse

- JSON.stringify

- document.getEementById 

- DOM traversal algorithm(DOM 순회 알고리즘)

- data structures

- cleaner alternative to iteration

 

DOM traversal algorithm(DOM 순회 알고리즘)

DOM의 모든요소가 중첩된 트리 구조로 되어있기 때문에 만약 div 태그안에 div가 들어있고 이러한 중첩 계층이 100개나 될때 그것을 살펴보고자 할때 흔한 접근법 중 하나가 재귀적으로 코드를 작성하는 것이다.

Data structures

또한 데이터구조/트리/그래프를 순회하고 그안에 있는 요소를 검색하고자 하는 경우 솔류션에 재귀가 포함될때가 많다.

cleaner alternative to iteration

또한 재귀적으로 작성할 필요는 없지만 재귀적으로 작성할때 더 쉽고, 깔끔하기 때문에 이해하기도 편하다. 따라서 이러한 재귀적으로 사용하는 것은 모든 곳에서 사용되고 있기 때문에 이를 이해할 필요가 있다. 

 

---

 동작원리

만약 재귀함수가 자기자신을 계속해서 호출하고 또 호출한다면, 우리가 볼 수 없는 곳에서는 어떻게 처리되는지 살펴보고자 한다.

 

대부분의 프로그래밍 언어는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다. 호출된 함수는 다른 함수가 반환(return)될 때까지 기다리는 경우가 많고 랜덤하게 순서없이 함수가 실행되는 일이 없다. 재귀함수에서도 먼저 호출한 함수가 있고 그 함수안에서 두번째로 함수를 호출한다. 

 

호출스택(Call Stack)

이럴때 올바른 순서로 함수가 실행되야하고 이걸 담당하는 것이 데이터 구조이다. 자바스크립트 경우는 호출스택(Call Stack)이 이에 해당하는 정적 데이터 구조이다. 아마 이전에도 스택과 큐에 대한 글을 쓴적이 있는데 함수를 호출하면 호출스택의 꼭대기에 쌓이게 된다. 마치 종이 더미처럼 우리가 새로 추가하는 함수가 있다면 제일 꼭대기 위에 쌓이며 위치하게 되는 것이다.

 

그렇게 순서에 맞는 함수를 실행하고 return을 확인하거나 더이상 함수안에서 실행할 코드가 없으면 컴파일러가 스택의 제일위에 있는 이 함수를 제거(pop) 한다.

 

Chrome 개발자 도구를 이용하여 실제로 호출된 함수가 몇개 있고 스택이 어떤 모습인지, 함수를 어떻게 반영하는지 확인할 수 있다.

위에는 서로다른 함수를 스택이 쌓이는 순서에 맞게 맨위에 쌓이는걸 확인할 수 있는데, 재귀함수의 경우는 자기자신을 계속해서 스택에 쌓고 호출을 기다리게 된다.

---

사용 예시

1. 카운트다운

// Recursive Version
function countDown(num){
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}
countDown(3)

// Iterative Version
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

위의 코드처럼 카운트다운을 한다고할때 재귀함수로 사용하는 방법말고 for문으로 사용할 수도 있지만 그것과 별개로 재귀함수로 어떻게 사용하는지 알기위한 예시 코드이다. 재귀함수가 끝나는 시점의 if조건을 주고 return으로 끝내는 걸 확인할 수 있는데 재귀가 멈추는 시점을 Base Case(종료조건)라고한다.

2.

 

function sumRange(num){
   if(num === 1) return 1; 
   return num + sumRange(num-1);
}

sumRange(4)

두번째 예시는 첫번째 예시를 이해했다면 쉽게 이해할 수 있다. base case는 num값이 1일때 1을 반환해주면서 재귀함수를 끝내고 그게아니라면 num값 + num-1로 재귀함수 호출한 값을 더해서 return 한다. 풀어서 해석한다면 sumRange(4)라고 재귀함수를 호출한다면.

4 + sumRange(3) + sumRange(2) + sumRange(1)이 되고 4+3+2+1 의 합계인 10을 반환해주는 재귀함수가 된다. 크롬 개발자 도구로 보면 다음과 같다.

이를 통해서 그전에 썼던 글중 팩토리얼도 이러한 재귀함수 방식으로 사용할 수 있는 것이다.

---

재귀함수의 잠재적 위험

- No Base Case/ Wrong Base Case

- Wrong Recursion Return 

- Stack Overflow

만약 Base Case를 넣지 않거나 잘못된 Base Case라면 계속해서 콜스택을 쌓아가게 되고 이렇게 되면 다음과 같은 에러가 난다.

이는 최대 호출 스택 크기를 초과했기 때문이다.