재귀함수

컴퓨터 과학에서 재귀란 자기 자신을 계속 호출하는 것을 의미한다.

제곱근을 구하는 함수는 보통 for문을 사용한다.

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

console.log(pow(2,3));   // 8 

하지만 재귀함수를 사용하면 다음과 같이 구현할수 있다.

function pow(x,n){
  if (n==1) {
    return x;
  }
  else {
    return x*pow(x,n-1)
  }
}
console.log(pow(2,3));   //8

삼항 연산자를 사용하면 더 간결하게 가능

function pow(x,n){
 return (n==1) ? x : x * pow(x,n-1)
}
console.log(pow(2,3));

장점

그럼 재귀함수는 왜 사용하는걸까?

우선 코드가 짧다.

코드가 짧기때문에 유지보수가 좋아진다.

또 재귀적 순회가 가능한데 하위의 깊은 구간에도 쉽게 접근할수 있다.
for문으로도 접근할순 있지만 매우 지저분해지기때문에 권장하지 않는다.

단점

재귀 함수에도 단점이 있다.

재귀함수를 실행할때마다 실행컨텍스트에 저장되기때문에 메모리에 부담이 간다..
자바스크립트 엔진은 1만개 부터 10만개 이하 까지 엔진에 따라 제한을 둔다

tail calls optimization 라는 최적화를 하기도 하지만 간단한 경우에만 지원한다

구조

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

재귀의 베이스

재귀함수에서 가장 안쪽인 if n==1 부분을 재귀의 베이스라고 부른다.
여기서부터 중첩됬던 실행컨텍스트를 하나씩 지우면서 외부로 리턴한다

재귀 깊이

중첩호출의 갯수를 재귀 깊이라고 한다. 여기서는 재귀 깊이는 n이다

재귀 단계

x * pow(x, n - 1) 자기 자신을 호출할때를 재귀 단계 라고 부른다.

출처 https://ko.javascript.info/recursion#ref-1035