[JavaScript] 함수 - 재귀와 스택

재귀(recursion)

큰 목표 작업 하나를 동일하면서 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴

문제 해결을 하다 보면 함수에서 다른 함수를 호출해야 할 때가 있는데 함수가 자기 자신을 호출하는 것이 재귀.

 

x를 n제곱하는 함수 만들기

[ for 반복문으로 만들기 ]

<script>
  function pow(x, n) {
    let result = 1;
    for (let i = 0; i < n; i++) {
      result *= x;
    }
    return result;
  }

  console.log(pow(2, 5)); //32
</script>

 

[ 재귀적 사고로 만들기 ]

<script>
  function pow(x, n) {
    if (n == 1) {
      return x;
    } else {
      return x * pow(x, n - 1);
    }
  }

  console.log(pow(2, 5)); // 64
</script>

 

pow(x, n)함수는 ( n이 1이 아닐 때)의 경우에서 내부에 있는 자기 자신을 반복 호출하면서 값을 찾아간다.

 

x = 2

n = 5

 

n이 1이 아니기 때문에 함수는 2 * pow(2, 4)를 실행하는데 n이 1이 될 때 까지 반복해서 호출한다.

---

n이 1이 되는 순간의 식은

 

2 * 2 * 2 * 2 * pow(2, 1)

 

이며 pow(2,1)은 2를 반환하므로 결과적으로

 

2 * 2 * 2 * 2 * 2 가 된다.

---

즉 n은 1이 될 때가지 재귀적으로 본인을 호출하며 그 동안 자기 자신의 함수 또한 점점 간단해지고 결과값을 반환한다.

 

가장 처음 하는 호출을 포함해 중첩 호출의 최대 개수를 '재귀 깊이'라고 하며 pow(x, n)의 재귀 깊이는 n.

 

자바스크립트는 재귀 깊이를 제한하는데, 10,000개까지는 대체적으로 허용되며 엔진에 따라 약간의 차이는 있다.

대다수의 엔진이 재귀 깊이 100,000까지는 수행하지 못하지만 그럼에도 간결하고 짧은 코드로 유지 보수를 할 수 있기 때문에 재귀는 광범위하게 사용되는 편.

 

---

실행 컨텍스트와 스택

재귀 호출의 과정을 알려면 함수의 내부 동작에 대해 알아야 한다.함수가 실행되면 함수 실행에 대한 내부 정보가 '실행 컨텍스트(execution context)'에 저장되는데

 

함수 호출 1회 당 정확히 하나의 실행 컨텍스트가 생성된다.

 

<중첩 함수가 호출 될 때 순서>

1. 현재 함수 실행 일시 중지.
2. 중지된 함수와 연관된 실행 컨텍스트는 실행 컨텍스트 스택(execution context stack) 이라는 특별한 자료 구조에 저장
3. 중첩 호출 실행.
4. 중첩 호출 실행이 끝난 후 실행 컨텍스트 스택에서 일시 중단한 함수의 실행 컨텍스트를 꺼내고, 중단한 함수의 실행을 다시 이어갑니다.