[Development] Recursion

재귀함수

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 설명할 때 자기를 포함한 것이라고 생각하면 편하다. 그냥 자기를 설명할 때 나는 나야 나라는 건 나야 이렇게 설명하는 것이라고 볼 수 있다.

-나무 위키

정의는 무지하게 쉽다. 내가 나를 부르면 되는 것이다.

---

재귀 함수와 콜 스택

함수를 호출하면 콜 스택이라는 곳에 함수가 stack으로 쌓인다.

즉, 최상위에 함수가 끝날 때까지 그 아래에 있는 함수는 남아 있다는 것이다.

function c(){
  console.log('C');
}
function b(){
  console.log('B');
  c();
}

function a(){
  console.log('A');
  b();
}

a();

// call stack에는?

 

일반적으로 함수가 실행되는 과정

일반적으로 함수가 실행되는 과정

재귀 함수를 이런 식으로 부르면 어떻게 될까??

function recursiveFunc() {
  console.log("재귀함수 실행");
  recursiveFunnc();
}

recursiveFunnc();

 

계속계속 stack에 쌓인다...끝도없이

callstack도 자료를 담을 수 있는 자료구조다. 그 크기가 무한할 수가 없다. 결국엔 callstack이 넘쳐 에러가 날것이다.

이 에러를 stack over flow라고 부른다.

---

프로그래밍 언어에서 재귀 함수는 종료 조건에 크게 의존한다.

최상위 스택의 함수가 끝나야만 그 아래에 있는 함수들이 끝나기 때문이다.

재귀 함수를 쓸 때는 항상 종료 조건과 재귀 조건을 써야 한다.

function recursiveFunc(n){
  if(n === 1){ // base case
    return n;
  }else{
    return n * recursiveFunc(n-1);  // recursive case
  }
}

이 코드는 재귀 함수를 설명할 때 단골로 나오는 코드이다. 팩토리얼을 구하는 것이 재귀적으로 해결하기 딱 좋은 경우이기 때문이다.

계속 자기 자신을 부르면서 n이 1씩 작아지는 것을 볼 수가 있다.

이 부분이 가장 중요한데, n이 base case에 조건이 되면 실행된 그 함수가 CallStack 최상위에 있는 함수가 되고, 리턴되면서 아래 함수에 n값을 전해준다. 

아래 함수에서 n 값을 받으면 그 값으로 처리하면 되는 것이다. 이 부분이 recursive case가 되는것이다.

여기서는 1씩 줄어들기 전 n값과 리턴 받은 값을 곱해서 return 해준다.

---

 

팩토리얼의 재귀 함수를 통해서 재귀를 이해했다면 병합 정렬의 재귀 방식도 쉽게 이해할 수가 있다.

병합 정렬은 대표적인 분할 정복을 이용한 정렬 방식인데, 자세한 설명은 여기를 참조하면 된다.

https://artdev.tistory.com/77

function mergeSort(array) {
  if(array.length <= 1){
    return array;
  }else{
    // 배열을 반으로 잘라서
    const midIndex = Math.floow(array.length/2);
    
    // 잘린 배열을 받는다.
    const rigthArray = mergeSort(array.slice(0,midIndex));
    const leftArray = mergeSort(array.slice(midIndex));
    
    // 정렬된 값을 저장할 배열
    const resultArray = [];
    
    // 배열을 가지고 정렬해준다.
    // 기본적으로 0번째 인덱스끼리만 비교해준다. (mutable메소드 사용)
    // 왼쪽과 오른쪽 모두 값이 존재할때
    while(rightArray.length && leftArray.length){
      if(rightArray[0] < leftArray[0]){
        resultArray.push(rightArray.shift());
      }else{
        resultArray.push(leftArray.shift());
      }
    }
    // 왼쪽에만 배열만 있을때
    while(leftArray.length){
      resultArray(leftArray.shift());
    }
    // 오른쪽에만 배열이 있을때
    while(rightArray.length){
     resultArray(rightArray.shift()); 
    }
  }
  // 다 정렬시켜서 아래에 있는 함수에 리턴
  return resultArray;
}

최상위 스택에서부터 배열이 하나씩 리턴되고 그 값으로 계산해서 최종적으로 정렬된 배열이 나온다.

재귀에 익숙해지면 각 스택에 있는 과정을 생각하지 않고도 코드를 짤 수 있다고 하는데 나는 아직 그런 레벨은 아닌 것 같다. 

하나하나 다 짚어가면서 봐야 이해가 가는 수준이다.

 

언젠가는 그런 정도의 레벨이 되었으면 좋겠다.