자바스크립트 핵심컨샙33 #23. Recursion(재귀 함수)

컴퓨터 과학에 있어서 재귀(再歸, Recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.
feat.wiki

재귀 함수란 쉽게말해 '자기 자신을 호출 하는 함수'를 뜻합니다.
자기 자신을 호출하는 패턴은 유용한 프로그래밍 기법입니다. 중복을 없애며 코드 스타일을 단순화 합니다.

보통 반복적인 코드를 구현하는 방법은 '반복문'을 이용하는 것입니다.

function func(x, n) {
  let res = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

console.log(func(2,3))//8

x를 n 제곱해 주는 함수를 for문을 이용하여 구현하였습니다.

이번엔 재귀를 통한 반복을 해보겠습니다.

function func(x, n) {
  if (n == 1) {//재귀 종료 조건문
    return x;
  } else {
    return x * func(x, n - 1);//자신을 호출 할 때마다 n의 숫자를 줄임 
  }
  //즉 2 x 2₂이 됩니다.
}

console.log(func(2,3))//8

저번 포스팅에서 설명했던 '호출 스택'을 이해했다면 재귀 함수가 어떤 순서로 진행되는지 이해가 빠를것입니다.

재귀 함수를 설명할 때 가장 많이 등장하는 예제 코드가 바로 팩토리얼 구하기입니다.

팩토리얼이란 자기 자신부터 시작해서 1 감소한 숫자들을 곱한 값입니다.

function func (x) {
	return x * func(x - 1);
}

console.log(func(5))
//Uncaught RangeError: Maximum call stack size exceeded

하지만 이렇게 작성하면 오류가 납니다.

저런 식으로 '중단점'이 없이 재귀함수를 호출하면 호출 스택의 사이즈가 초과되어서 오류를 발생시킵니다. 이것을 '스택오버플로우'이라고 부릅니다. 바로위 코드에서 적었던 '재귀 종료 조건문'이 이런 스택오버플로우를 종료하는 문장이며 이것을 'Base Case'라고 합니다.

function func (x) {
  if (n === 1) {
    return 1;
  }
  
  return x * func(x - 1);
}

console.log(func(5))//120

Basc Case를 작성하여 스택오버플로우를 막았습니다. 일반적인 반복문보다 훨씬 가독성도 좋고 유지보수도 수월합니다.

마지막으로 피보나치 수열을 통해 재귀함수를 구현해보겠습니다.
먼저 일반적인 반복문으로 구현을 했습니다.

function func (x) {
  if (x < 2) {//2보다 작은 순서는 그 값을 리턴함
    return x;
  }
  
  let temp = 0;//일시적인 현재값
  let cur = 1;//현재값
  let last = 0;//지난값
  
  for(let i = 1; i < x; i++){
  	temp = cur;
    cur += last;
    last = temp;
  }
  
  return cur
}

console.log(func(10))//34

이번엔 재귀 함수입니다.

function func (x) {
  if (x < 2) { 
    return x;
  }

  return func (x - 1) + func (x - 2)
}

console.log(func(10))//34

훨씬 깔끔해진것을 볼 수 있습니다!