Algorithm_1. 재귀

Seoyong Lee·2021년 5월 11일

Algorithm / Data Structure

목록 보기

2/22

재귀의 개념

재귀(recursion)는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 재귀는 중첩의 정도(number of loops)를 알 수 없는 상황에서 유용하게 사용될 수 있으며, 비슷한 구조를 유지하면서 작은 규모로 나누어질 수 있는 문제의 해결에 적합하다. 또한 함수형 프로그래밍에서는 반복문을 재귀 함수로 대체하여 작성하기 때문에 이러한 재귀의 개념을 이해하는 것은 중요하다.

재귀와 반복문

만약 어떠한 행동을 반복적으로 진행해야 한다면 어떠한 방법을 사용해야 할까? 크게 반복문과 재귀라는 두 가지 방법을 사용할 수 있다. 다음의 예시를 통해 두 방법의 차이와 특징을 확인할 수 있다.

num과 같거나 작은 모든 양의 정수의 곱을 구해주는 함수 factorial(num)이 있다고 가정하자. 이는 아래의 결과를 만족해야 한다.

factorial(3) = 6
factorial(6) = 720

이는 다음 두 방법을 이용해 구현할 수 있다.

// for 반복문 사용
function factorial(num) {
  for (let i = num - 1; i >= 1; i--) {
    num *= i;
  }
  return num;
}

alert( factorial(3) );

위는 일반적인 반복문이다. num - 1 부터 1 까지 반복하며, for 문 안에서 각각의 i(iteration)를 다시 num에 곱해주면서 답을 구한다.

// 재귀를 이용한 방법
function factorial(num) {
  if (num <= 1) {
    return 1;
  }
  return num * factorial(num - 1);
}

alert( factorial(3) ); // 6

위와 같이 재귀를 이용하면 두 가지 조건으로 분리할 수 있다.

만약 num이 1이 되면 1을 리턴한다.
위 조건을 만족할 때 까지 num-1을 대입한 factorial 함수를 재귀적으로 호출하며, 이 값과 num(자기 자신)을 곱한 값을 리턴한다.

// for 반복문의 구조
function factorial(num) {
  for (begin; condition; step) {
    body
  }
  return // 결과값
}

// 재귀 함수의 구조
function factorial(num) {
  if (condition) {
	
  }
  return begin * factorial(step);   // body, 결과값
}

쉽게 말하면 위 재귀함수는 base 상황일 때 중단하며(condition), num에서 부터(begin) 1씩(step) 작아진 수를 계속해서 곱하는(body) 반복문과 같다.

이러한 재귀함수를 구성하는 방법은 다음과 같다.

재귀적 사고

1. 입력값과 출력값의 정의

먼저 재귀 함수의 입력값과 출력값을 정의한다. 예를 들어 팩토리얼을 반환하는 재귀 함수 factorial의 입력값은 숫자이고, 출력값은 지금까지 입력된 숫자를 모두 곱한 수이다.

2. 문제 분리

다음으로 문제를 작은 단위로 분해해 본다. 만약 같은 방식으로 크기만 줄여나갈 수 있다면 이를 재귀에 대상으로 설정한다. factorial의 경우 4를 입력한 경우와 3을 입력한 경우 동일하게 해당 숫자부터 1까지의 곱을 반환한다. 그렇다면 '해당 수 부터 1까지 곱한다'라는 행동을 재귀를 통해 반복할 수 있다. 이렇게 반복할 행동 설정이 완료되면 재귀의 기초(base: 곱할 수 있는 가장 작은 수)를 구한다.

3. 단순한 문제 해결

재귀의 기초(base case)는 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)으로, 가장 마지막에 남는 결과이다. 위 factorial의 예시에선 1보다 작은 수를 곱하면 0이 되므로, 1이 바로 재귀의 기초이자 탈출 조건이 된다.

4. 복잡한 문제 해결

이제 나머지 기초를 제외한 나머지를 구하는 식을 구성한다. factorial의 경우 1부터 자기 자신까지 계속해서 곱한 뒤 탈출 조건을 만나 종료되어야 한다. 이를 코드로 표현하면 다음과 같다.

function factorial(num) {
  if (num <= 1) {
    return 1;
  }
  return num * factorial(num - 1);
}

코드를 살펴보면 factorial 함수는 num을 받아 if 문에서 탈출 조건을 확인한 뒤, num과 factorial 함수의 곱을 반환한다. 이때 리턴문의 factorial 함수 인자는 자기 자신에서 1을 뺀 수로, 이러한 과정을 반복하면 결국 num은 1이 되어 재귀를 탈출한다. 최종적으로 factorial 함수는 1부터 num까지의 수를 모두 곱한 결과를 리턴한다.

이를 더욱 자세히 분해하면 다음과 같다. num이 3이라고 가정하자.

function factorial(3) {
  if (3 <= 1) {
    return 1;
  }
  return 3 * { // 2 -> 최종 6 리턴 
    if (2 <= 1) {
      return 1;
    }
    return 2 * { // 1
      if (1 <= 1) {
        return 1; // 탈출 조건 확인 ! 
      }       
    }
  }
}

응용 사례

이러한 재귀는 다양한 문제에 적용할 수 있다. 대표적인 것이 바로 위의 예시와 같은 '팩토리얼'로 재귀 함수를 구성하면 쉽게 1부터 해당 숫자까지의 곱을 구할 수 있다. 재귀는 또한 '피보나치 수열'과 하노이의 탑 문제의 해결에 도움을 준다. 또한 재귀는 DOM에서 응용될 수 있는데, 같은 구조가 중첩된 트리 UI의 제작에 사용될 수 있다.

(예시 코드 추가 예정)