[알고리즘 | JS] 재귀함수에 대해 알아보자! (호출스택, 스택오버플로우)

🍕recursion(재귀)가 무엇일까?

-자기 자신을 호출하는 절차이다. 

-우리의 경우는 재귀(함수)는 자기 자신(itself)을 호출하는 함수를 의미한다.

 

🍕재귀가 적용된 예시 

• JSON.parse/ JSON.stringify 
  • 해당 메소드들은 자바스크립트 엔진으로 실행된다. 모질라(mozilla)의 경우는 라이노(Rhino)라는 자체 실행 엔진이 있다. 이러한 엔진에서 JSON.parse를 원하는대로 작성하는데, 꼭 재귀적으로 작성할 필요는 없다. 하지만, 보통 재귀적으로 작성하는 경우가 많음
• documnent.getElementById 와 DOM traversal algorithms (돔 순회 알고리즘)
  • DOM은 모든 요소가 중첩된 트리 구조로 되어있다는 것을 명심하자
  • e.g. div안의 div가 들어있는 중첩 계층이 100개나 될 수 있다.
• Object traversal(객체순회) 
  
  • 객체 순회는 순회 JSON과 비슷하다.
  • e.g. 기존에 사용하던 JSON.parse , getElementById , querySelector 같은 내장 함수도 있지만 나중에 많은 재귀 함수를 직접 작성할 것임(직접 트리순회하는 것을 만들 거나 할 때)

-> 때로는 반복(iteration)대신 재귀를 사용하는 게 더 깔끔하다.

---

재귀함수를 직접 만들어보기 전에 함수의 작동에 대해 알아보자.

 

🍕함수의 작동 원리

-거의 모든 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 있다. 
-호출된 함수는 다른 함수가 반환(return)될 때까지 기다리는 경우가 많다. 그래서 함수의 순서가 있고 이걸 처리하는 데이터 구조가 따로 있다. 
자바스크립트의 경우에는 호출 스택(call stack)이 그 역할을 한다. 

🍕자바스크립트의 호출스택(call stack)? 

-호출 스택은 종이 더미같은 것이라고 생각하면 편하다. -> 실제로는 스택(stack)이라는 데이터 구조이다.

*종이 더미라고 한 이유는 종이를 꺼낼 때 항상 맨 위부터 꺼내기 때문

-호출 스택은 자바스크립트의 보이지 않는 곳에서 작동하는 정적 데이터 구조(static data structure)이다. 

• 정적 데이터 구조? 항목이 꼭대기에 추가되고 마찬가지로 꼭대기부터 제거되며 함수가 호출되면 이 구조에 추가된다는 의미 //  LIFO(Last In First Out) 형식의 자료 구조

-모든 함수는 호출스택에서만 실행되며 싱글 스레드이다.

 

🍕호출 스택과 함수

• 함수를 호출하면, 호출 스택의 꼭대기에 쌓인다(pushed). -> 새로 추가하는 함수가 제일 꼭대기에 위치하게 됨
• 자바스크립트가 반환 키워드(return keyword)를 확인하거나, 함수 안에 더이상 실행할 코드가 없으면 컴파일러(compiler)가 스택의 제일 위에 있는 항목을 제거(pop, 꺼내기)한다. 

🍞함수가 호출될 때 콜스택 확인하기

-자바스크립트 개발자도구(F12)를 통해서 실행시킨 함수가 콜스택에 쌓이고 어떤 순서로 작동되고 리턴값이 뭔지 지역변수가 뭔지 등등을 눈으로 확인할 수 있습니다. 재귀함수의 작동원리는 기존의 함수호출과 다르기 때문에 해당 도구를 사용해서 작동을 눈으로 파악하면 도움이 된다. 

• 원하는 함수에 break포인트를 걸고 한 단계씩 버튼(우측)을 눌러서 함수가 호출될 때 콜스택의 모습과 scope를 확인할 수 있다. 

 

---

🍕재귀 함수의 작동은 어떻게? 

-종료 조건에 도달할 때까지 다른 입력값으로 동일한 함수를 호출한다.

(Invoke the same function with a different input until you reach your base case)

// 동일한 함수를 계속 호출하면서, 하나의 함수가 자기자신을 재귀적으로 호출하게 하는 것

Base Case(문맥상: 종료 조건을 의미, 중단점)
: 재귀가 멈추는 시점을 의미한다. 

🍕재귀 함수의 필수 조건 2가지

1. 중단점( 종료 조건 , base case)  e.g. 함수에서는 return 
   • 보통 종료 조건(base case)에는 무언가를 찾기 위한 조건이 포함되고, 어떤 값을 반환한다.
2. 다른 입력값

🍔사용하지 않는 함수 vs  재귀를 사용하는 함수 비교하기

//naive solution
{
  //단순히 for문
  function countDown(num) {
    for (let i = num; i > 0; i--) {
      console.log(i);
    }
    console.log('all done!');
  }
  countDown(5);
}
{
  //재귀함수 예시1 
  function countDown(num) {
    if (num <= 0) {
      console.log('all done');
      return;
    }
    console.log(num);
    num--;
    countDown(num);
  }
  countDown(3);
  //실행 순서
  /*
  print 3
  num-- // 2 
  countDown(2)호출
  print 2
  num-- // 1 
  countDown(1)
  print 1 
  num-- // 0
  if절 실행 -> all done return; 끝. 
  즉, if절(num <= 0)에서 return이 꼭있어야 한다. 중단점(base case)!
  */
}

재귀 함수 예시2

{
//재귀함수 예시2 
  //해당 예시에서는 return이 2개나 있어서 헷갈릴 수 있는데
  //첫줄의 if절은 조건에 부합할 때 멈추는 구간이다.

  function sumRange(num) {
    if (num === 1) return 1; //중단점 breakpoint
    return num + sumRange(num - 1);
  }
  console.log(sumRange(3)); // 6, 3+2+1
  //실행 순서
  /*sumRange(3)
    return 3 + sumRange(2)
                return 2 + sumRange(1)
                                return 1
                                역순서로 값을 더해간다. 
                                */
}

 

콜스택을 보면 return값을 기다리는 재귀함수가 쌓여있다.

-> 우리가 return값을 정확히 아는것은 sumRange(1)이므로 역순서로 연산이 된다.  

sumRange(2),sumRange(3)는 리턴값을 기다리고 있어서 위와같이 쌓여있다.

 

팩토리얼 만들기 (비재귀, 재귀함수 비교)

{
  //factorial 만들기
  //for 문을 사용해서 만들기, 비재귀적 solution, 반복 솔루션
  function factorial(num) {
    let total = 1;
    // for문에 i > 0 -> i > 1로 수정, total이 1이기 때문에 굳이 중복을 할 필요없다.
    for (let i = num; i > 1; i--) {
      total *= i; // total = total * i  와 같음
    }
    return total; //for문을 나올 때 total을 리턴
  }
}
{
  //factorial 만들기
  //재귀함수로 만들기 (재귀 팩토리얼)
  //중요한 점은 큰 부분을 작은 부분으로 나눠서 하는 것
  function factorial(num) {
    //factorial(3)는 factorial(2) * 3과 같음
    //factorial(2)는 factorial(1) * 2와 같음
    if (num === 1) return 1; //중단점
    return num * factorial(num - 1);
  }
  console.log('재귀 팩토리얼의 결과 값은' + factorial(10));
}

---

🍕통상적인 재귀의 잠재적 위험(스택 오버플로우를 발생시키는 원인)

🍔재귀함수에 중단점(break point, base case)이 없는 경우

-> 내부적으로 자기자신을 계속 호출하기 때문에 최대 스택 크기 초과 에러가 뜹니다. 

( Uncaught RangeError : Maximum call stack size exceeded )

콜스택의 최대 크기는 노드(node)인지, 어떤 엔진을 사용하고 있는지 등에 따라 달라진다. 
chrome의 최대 스택 크기 초과 에러를 스택 오버플로우(stack overflow)라고 부릅니다. 
즉, 스택 오버플로우는 '재귀가 멈추지 않는다'는 의미입니다.

🍔애초에 반환하는 것을 잊을 경우 -> 리턴값이 따로없이 콘솔에 1만 출력하기 때문에 콜스택 에러 발생

if (num === 1) console.log(1); //리턴값을 까먹는 경우, 여기엔 return이 없다.

 

🍔잘못된 값을 반환하는 경우 -> 중단점에 도달할 수 없어서 콜스택 에러 발생

return num * factorial(num); //잘못된 값을 반환 num * factorial(num)은 중단점에 도달할 수 없다.

결론

호출 스택이라는 개념은 모든 항목이 서로에게 의존하면서 계속 기다리는 것이다. chain으로 연결된 것 같다고 생각하면 된다. 어쨌든 마지막에는 어떤 값을 도출해서, 그 값을 돌려보내야 한다.

• 위의 3가지 경우는 스택 오버플로우를 발생시키는 원인들이다.