Recursion [재귀]

1. Recursion (재귀)

 

재귀 함수란: 함수 안에서 자기 자신을 다시 호출하는 것을 말한다.

1 - 1. Recursive vs Iterative

 

보통의 Recursion (재귀)를 사용할 수 있는 문제들은 Recursive 또는 Iterative 둘 중 어느 한 방법으로도 해결할 수 있다.

 

먼저, Iterative (반복적인) 함수는 우리가 일반적으로 사용하는 for문이라 forEach와 같은 반복연산을 사용한다.

 

반면에, Recursive 함수는 성능은 조금 떨어질지 몰라도 코드가 훨씬 가독성이 있다는 점에서 많이 사용된다.

 

1 - 2. What Is Recursion?

 

재귀 함수를 설명할 때 일반적으로 팩토리얼 (Factorial) 구하기를 예제로 많이 사용한다.

팩토리얼이란 자기 자신의 수에 1 작은 수를 곱하는 것을 반복해, 마지막 1 작은 수가 1 이 될 떄까지 곱하는 방식이다.

 

예를 들어, 5! = 5 * 4 * 3 * 2 * 1 = 120

5의 팩토리얼은 120 이 나오게 되는 것이다.

 

이 팩토리얼을 Iterative한 방법으로 먼저 코드를 적어봤다.

function factorial (n) {
  var result = 1;

  for (var i = n; i >= 1; i--) {
result = result * i;
}

  return result;
}

 

 

위 방법을 재귀적으로 생각해보면 이렇다.

factorial(5) = 5 * 4 * 3 * 2 * 1 = 5 * factorial(4);

factorial(4) = 4 * 3 * 2 * 1 = 4 * factorial(3);

factorial(3) = 3 * 2 * 1 = 3 * factorial(2);

factorial(2) = 2 * 1 = 2 * factorial(1);

factorial(1) = 1;

 

위 나열된 것들을 정리하면 이렇다.

factorial(n) = n * factorial(n - 1);

 

팩토리얼 함수를 만들어 콘솔창에 입력하여 4의 팩토리얼을 구해봤더니 아래 이미지와 같은 에러가 발생됬다.

 

Factorial(4)를 콘솔창에서 실행한 결과

Maximum call stack size exceeded. '최대 호출 스택 사이즈가 초과되었다' 라는 에러인데 이것이 바로 우리가 주의해야하는 부분이다.

재귀 함수는 특정 탈출 조건이 없다면 자기 자신을 에러가 날 때까지 무한대로 계속해서 호출하여 실행한다.

이를 방지하기 위해 우리는 탈출 조건, 즉, 재귀 호출을 탈출시키는 문장이 반드시 존재해야 하는데,

이를 Base case 또는 Termination case라 부른다.

또한 이러한 이유로, 재귀함수를 사용할 때 '재귀적으로 생각하는 것'이 중요하다.

재귀적으로 생각하여 문제를 더 이상 쪼갤 수 없을 때까지 계속 문제를 단순화 시키면 복잡한 문제도 풀 수가 있게 되고,

탈출 조건을 작성하는데 큰 무리가 없다는 점이다.

 

그럼 탈출 조건을 포함시켜 새로운 코드를 만들어보자.

function factorial (n) {
  if (n === 1) { //Base case, 탈출 조건
    return 1;
}

  return n * factorial(n - 1);
}

factorial(3); //6

우리가 이전에 만들었던 코드에서 n === 1 이되면 1 을 반환시키는 조건이 추가되었다.

그러므로, n === 1 이 되면 반복이 멈추고 우리가 원하는 팩토리얼의 값을 얻을 수 있게 된다.

---

이번 TIL을 마치며...

 

재귀의 강력함과 재귀의 구조 등을 심화적으로 알아볼 수 있고, 몇 가지 추가 예제를 통해 재귀를 공부할 수 있는 사이트다.

유용한 정보와 예제들이 많아 천천히 그리고 꼼꼼히 읽어볼 계획이다.

 

링크: ko.javascript.info/recursion

재귀와 스택