2024년 01월 08일 월요일

재귀(recursive) 알고리즘

들어가며

지난 시간까지 우리는 빅오, 알고리즘이란 무엇인가, 간단한 문제 풀이 알고리즘에 대해서 배워보았습니다.

이를 통해 알고리즘이란 무엇이며, 알고리즘이 컴퓨터에서 어떻게 활용되는지에 대해서 감을 잡는 시간을 가졌습니다. 이렇게 익힌 감각을 바탕으로 이번 시간부터는 본격적으로 핵심 알고리즘들을 배우고, 이를 기반으로 해서 코딩 테스트 문제들을 몇 가지 풀면서 익히는 시간을 갖고자 합니다.

많은 알고리즘들 중에서 제일 먼저 배울 것은 재귀(Recursion)입니다. 이는 재귀함수(Recursion)이라고도 불립니다.

그러면 이게 무엇인지 같이 살펴봅시다.

재귀(Recursion)

그림으로 이해해보는 재귀

위의 그림을 한번 살펴봅시다.

어떤게 느껴지시나요? 계속 확대를 하고 있는데, 특정 패턴이 무한하게 반복되는게 느껴지시나요?

재귀의 대표적인 예시 중 하나인 프렉탈(fractal)입니다.

그림은 재귀의 핵심적인 요소를 명확히 보여주고 있는데 어떤 것인지 감이 잡히시나요?

재귀의 정의

먼저, 우리나라 사전에서는 재귀를 어떻게 정의하고 있는지 살펴볼까요?

원래의 자리로 되돌아가거나 되돌아옴.

표준대국어사전

유의어로는 귀소, 컴백이 있고, 예문으로는 "연어는 산란을 하기 위하여 태어났던 강으로 재귀한다" 라고 표시되어 있습니다.

일반적인 정의는 위와 같으나, 저희가 사용하는 재귀 혹은 재귀 함수에 사용하는 용어는 조금 다릅니다.

아래의 정의를 봅시다.

수학과 컴퓨터 과학에서 재귀적 정의 또는 귀납적 정의는 집합 내의 다른 원소를 통해 그 집합의 원소를 정의할 때 사용된다.

위키 백과 (Aczel, Peter(1977).《An Introduction to Inductive Definitions》

우리가 다루고자 하는 재귀는 위의 정의를 따릅니다.

재귀(Recursion) 라는 개념은 위에서 왔다고 봐도 무방합니다.

핵심은 "집합 내의 다른 원소를 통해서 그 집합의 원소를 정의할 때 사용된다." 입니다.

Recursionoccurs when the definition of a concept or process depends on a simpler or previous version of itself.

wikipedia (Causey, Robert L. (2006).Logic, sets, and recursion

위키피디아에서 가져온 내용입니다. 재귀란 개념이나 과정을 정의할 때, 자기 자신의 이전이나 단순한 버전에 의존하는 것이라고 정의가 되어있습니다.

자기 자신의 이전 요소에 의존해서 어떤 개념이나 과정을 정의하는 것.

이게 곧 우리가 다룰 재귀의 전부입니다.

그림으로 다시 이해해보기

아래와 같이 선분이 있다고 해봅시다.

위와 같은 선분의 중앙에 삼각형을 배치한다고 생각을 해봅시다.

그러면 위와 같이 그려질 거에요. 여기에 다시 같은 작업을 해봅시다.

그러면 위와 같이 나타나게 됩니다.

이를 반복하면 어떻게 될까요?

위의 그림 처럼 나타나게 됩니다.

다시 말하면, 앞서 본 프렉탈의 규칙성을 "선분의 중앙에 삼각형을 배치한다" 라고 표현할 수 있는 것이지요.

어떤가요? 프렉탈이 위와 같은 규칙성을 갖고 있다는게 이해가 되시나요?

그러면 이를 머리에 두고, 앞서 언급한 정의를 살펴봅시다.

재귀란 개념이나 과정을 정의할 때, 자기 자신의 이전이나 단순한 버전에 의존하는 것

이 말을 위의 그림에 맞춰볼까요?

개념이나 과정 :: 프렉탈
을 정의 :: 규칙성을 표현하라
자기 자신의 이전이나 단순한 버전 :: 선분의 중앙에 삼각형 하나를 그린 것
에 의존하는 것 :: 이를 반복하면 프렉탈이 완성

이해되시나요? 결국은 프렉탈을 구성하는 일부분(선분의 중앙에 삼각형 하나를 그린 것)을 통해서 프렉탈을 표현할 수 있었습니다.

이는 프렉탈을 구성하는 한 요소이기도 하지만, 한편으로는 규칙이기도 합니다.

이것이 재귀입니다.

알고리즘 관점의 재귀

앞서서 재귀의 개념에 대해 살펴보았습니다.

이번에는 재귀가 문제 해결에 어떻게 활용이 되는 지 살펴보고자 합니다.

팩토리얼 문제

Q. 1부터 n까지의 곱을 구하는 함수를 작성하시오.

재귀를 신경쓰지 않고 위의 문제를 한번 풀어보시겠어요?

단순한 풀이

위의 문제를 어떻게 풀 수 있을까요?

의사코드
코드

n을 인자로 받는 multiply 함수를 선언한다.
함수 내부에 곱해진 값을 저장할 변수 result를 선언하고 1을 저장한다.
n부터 1개씩 줄여가면서 1까지 n번 반복한다. 이때 반복인자 i를 선언한다. (i는 n부터 1까지 반복될 때의 값을 나타냄)
3-1. result * n을 하고, 이를 다시 result에 저장한다.
result를 반환한다.

javascript
function multiply(n) {
  let result = 1;
  for (let i = n; i >= 1; i--) {
    result *= n;
  }
  return result;
}

제 나름대로 풀어봤어요.

이해가 되시나요??
이해가 안되어도 괜찮아요. 😄
같이 살펴보면서 하나씩 이해해봐요!

문제의 접근 방법

재귀의 방식으로 풀 때는 2가지가 중요해요.

종료조건
규칙

종료조건의 경우는 base case라고 많이 부르며, 재귀가 끝나는 지점을 명시해주는 조건이에요.

두번째로 규칙성인데, 이는 재귀적으로 반복할 규칙을 말해요. 코드로 표현해야하니 막연하고 추상적이면 안되고, 구체적이어야겠죠?

또한 앞에서 말한 재귀의 정의에 따라서 문제를 쪼개서 가장 작은 부분으로 표현해야해요.

그래서 가장 작은 부분을 반복하면 큰 문제가 해결이 되야하는 것이지요.

앞서서 표현한 프렉탈을 예로 들어볼게요.

이게 바로 규칙에 해당해요. 선분의 반절 지점에 삼각형을 그린다. 바로 이것이요.

언제 종료될지, 그리고 그 안에 규칙은 무엇일지 이것을 명확히 하는게 곧 재귀를 푸는 방법이에요.

규칙

그러면 문제로 돌아가서, 먼저 규칙을 찾아볼까요?

제가 알고리즘과 문제풀이법에서 강조했듯이, 어떤 문제상황이 주어졌을 때 제일 중요한 것은 문제를 읽고 분석하는거에요.

문제가 뭐였죠?

Q. 1부터 n까지의 곱을 구하는 함수를 작성하시오.

였었죠?

그러면 여기의 규칙은 무엇일까요?

한번 자신만의 말로 서술해보시겠어요?

바로 서술이 되면 잘하셨어요! 바로 서술이 되지 않더라도 하나씩 알아봐요.

규칙성을 찾을 때 중요한 것은 먼저 실제 사례를 바탕으로 나열해보는거에요.

$n$ 이 $1$ 이면 어떻게 될까요?

그냥 $1$ 이죠!

$n$ 이 $2$ 면 어떻게 될까요?

$1 * 2 = 2$ 겠죠?

n이 3이면 어떻게 될까요?

$1 * 2 * 3 = 6$ 이겠죠?

n	식	답
1	1	1
2	1 * 2	2
3	1 * 2 * 3	6
4	1 * 2 * 3 * 4	12
...	...	...

위와 같이 진행이 되고 있어요.

앞서서 언급한 재귀의 정의를 기억하시나요?

재귀란 개념이나 과정을 정의할 때, 자기 자신의 이전이나 단순한 버전에 의존하는 것

이라고 했었죠? 위의 진행을 단순화 시킬 수 있나요?

그리고 $n$ 까지의 곱을 구하는 경우를 $f(n)$ 이라고 합시다.

그러면 이를 이용해서 위의 진행을 표현할 수 있나요?

$n$ 이 $1$ 인 경우를 생각해봅시다.

$f(n=1) = 1$ 입니다.

$n$ 이 $2$ 인 경우를 생각해봅시다.

$f(n=2) = 1 * 2 = 2$ 입니다.

$n$ 이 $3$ 인 경우를 생각해봅시다.

$f(n=3) = 1 * 2 * 3 = 6$

...

이렇게 진행되는 것을 확인할 수 있습니다.

근데 잘 보면, $f(n=1) = 1$ 이니까, $f(n=2) = 1 * 2 = f(1) * 2 = 2$ 로 표현할 수 있지 않나요?

또한, $f(3) = 1 * 2 * 3 = f(2) * 3 = 6$ 으로 표현할 수 있지 않나요?

결국 이런 규칙성을 파악하면 $f(n) = f(n-1) * n$ 으로 표현할 수 있지 않나요?

이게 바로 규칙찾기 입니다.

사실 여기까지 보면 수학적 귀납법이 떠오르지 않나요?

앞에서 언급한 정의 중에 재귀적 정의와 귀납적 정의를 함께 다룬 이유를 아시겠나요?

사실 위처럼 표현한 규칙을 그대로 코드로 표현한게 바로 재귀 함수입니다. $f(n)$ 을 그대로 함수로 표현하기만 하면 되는 것이지요.

그러면 이제 규칙을 찾았습니다. 다음 스탭으로 넘어가봅시다.

종료조건

규칙을 찾았습니다. $f(n) = f(n - 1) * n$ 이라는 것을요.

그런데 여기에 문제점이 하나 생깁니다.

$f(1) = 1$ 이던거 기억하시나요?

그런데 위 식에 $f(1)$ 을 넣는 순간 값이 이상하게 나옵니다.

$f(1) = f(0) * 1$ 이죠.

$f(0) = f(-1) * 0$ 이고, 0에 무엇을 곱하든 0이니까, $f(1) = 0 * 1 = 0$ 이 됩니다.

혹은 $f(-1) = f(-1) * -1$

$f(-2) = f(-2) * -2$ ...

무한으로 반복되는 일이 생기는 것이지요.

즉, $f(2)$ 든 $f(3)$ 이든 뭐든 전부 0이라는 것이죠.

이를 예방하기 위해서 설정하는 게 종료조건입니다. 보통 base case라고 많이 부릅니다.

위 처럼 원치 않은 결과가 나오는 것을 막기 위해서 설정하는게 종료조건입니다.

재귀의 기본은 반복이기 때문에, 반복이 끝나는 시점을 명확히 해주는 것이지요.

앞서서 언급한 프렉탈 이미지 역시, 종료조건을 명확히 하지 않은 결과 끝나지 않은 반복이 이어지는 것입니다.

그러면 위 문제에서 종료 조건을 한번 설정해보시겠어요?

설정하셨나요?

종료 조건은 간단합니다. n이 1이하가 되는 순간들을 전부 1로 다루면서 종료하면 되는 것입니다.

즉, $n <= 1$ 인 경우 $1$ 을 리턴하는 형태로 구현하면 되는 것이지요.

이제 종료조건까지 끝이 났습니다.

코드로 표현하기

그러면 이제 이를 코드로 표현해보시겠어요?

위에 이미 답이 적혀있으니 따로 적지는 않을게요! 앞서 말한 규칙과 종료조건을 잘 생각해서 한번 코드로 구현해보세요!

왜 재귀인가?

그러면 재귀를 사용할까요?

지금부터는 재귀의 특징과 장단점에 대해서 알아보도록 해요.

재귀(Recursive) vs 반복(Iterative)

앞에서 본 문제처럼, 모든 재귀는 반복으로 표현할 수 있고, 모든 반복은 재귀로 표현할 수 있다는 특징이 있습니다.

재귀는 계속 함수를 호출하기 때문에 함수 호출에 따른 오버헤드가 걸립니다.

운영체제나 여타 CS 과목을 배우셨다면, 함수를 호출하면 스택에 쌓이고, 인터럽트가 걸리는 등 여러가지 작업이 필요하다는 것을 들어보셨을 겁니다.

배우지 않았더라도 함수를 호출하게 되면 무언가 추가적인 작업이 필요하다는 것을 알고 계시면 됩니다.

뭔가 작업이 필요하다는 것은 결국 자원을 쓴다는 것이고, 이게 반복되면 더 많은 자원을 요구하게 됩니다.

이처럼 재귀를 사용을 지양하고 가능하면 반복문을 활용하는게 좋습니다.

(실제로 제가 재귀로 문제를 풀었다가 "런타임 에러"가 발생해서 코테에 불합격한 경험이 있습니다..)

그렇다면 왜 재귀를 사용할까요? 재귀를 왜 배워야 할까요?

이 역시 이유는 명확합니다.

"가독성" 때문입니다.

위의 문제만 보더라도, 5줄짜리 코드가 3줄로 줄었습니다.

프로그램의 규모가 커지고, 작성된 코드가 많으면 많을수록 이런 차이는 명확해집니다.

AI가 아무리 발전한다고 한들 결국 개발은 사람손에 의해서 이루어집니다. 코드가 길면 길수록, 복잡하면 복잡할수록 이해하기 어렵습니다.

자신이 작성한 코드도 시간이 지나면 이해하는데 시간이 걸리는데, 협업을 하는 환경에서는 이런 문제는 더욱 크게 대두됩니다.

그렇기에 가능한 간단하게 표기하기 위해서 재귀를 사용합니다.

즉, 가독성과 보다 쉬운 유지보수를 위해서 사용하는 것이지요.

그렇지만 성능이 중요한 경우는 반복을 사용하는 경우가 많기에 둘 모두를 연습해두는게 좋습니다.

발전된 재귀

이제 한단계 더 들어가봅시다. 만약 재귀를 사용하는 과정에서 각각의 반복들이 공유해야하는 값이 있다면 어떻게 될까요?

전역변수 같은 게 필요하다고 하면 어떻게 할까요?

이제부터 이에 대해서 알아봅시다.

헬퍼 함수(Helper Function)

지금부터 알아볼 것은 헬퍼 함수(Helper Function)입니다.

재귀 함수 바깥에 또 다른 함수로 감싸서 함수 내부에서 재귀가 돌도록 만드는 것입니다.

위와 같은 형태로 말이죠.

문제

아래의 문제를 한번 풀어볼까요?

Q. n이 주어질 때, 1부터 n까지의 곱을 "n 까지의 곱 : 결과"의 형태로 표현하시오.

이를 한번 풀어보시겠어요?

풀이

재귀 부분은 위에서 이미 설명을 했기에, 바로 코드로 표현해서 이를 통해 같이 알아보도록 합시다.

javascript
function printMul(n) {
  function helper(n) {
    if (n <= 1) return 1;
    return helper(n - 1) * n;
  }

  const result = helper(n);

  return `n까지의 곱 : ${}`; // 단순 콘솔에 출력하는 요소
}

위와 같이 표현하는 것입니다.

즉 함수의 내부에서 재귀를 사용하는 것입니다.

재귀가 메인이 되는 것이 아니라 어떤 요소 내부에서 사용하는 것이죠.

사실 앞서 배운 재귀와 큰 차이는 없는데, 활용도 차이가 있어서 위와 같이 별도로 표기해보았습니다.

정리

이렇게 재귀에 대해서 알아보았습니다. 이해가 좀 되셨나요?

사실 얼핏 이해되더라도, 재귀는 직접 해보지 않으면 이해하기 어렵습니다.

그래서 문제를 한번 풀어보면 좋을 듯 해서 백준의 재귀 문제 모음에 대한 링크를 올리니 꼭 풀어보세요!

백준 문제

재귀의 경우에는 이후 DFS/BFS, 동적 프로그래밍, 분할 정복 등의 알고리즘에서 필수적으로 쓰이는 요소이기에, 꼭 익혀두시길 바랍니다.

들어가며​

재귀(Recursion)​

그림으로 이해해보는 재귀​

재귀의 정의​

그림으로 다시 이해해보기​

알고리즘 관점의 재귀​

팩토리얼 문제​

단순한 풀이​

문제의 접근 방법​

규칙​

종료조건​

코드로 표현하기​

왜 재귀인가?​

재귀(Recursive) vs 반복(Iterative)​

발전된 재귀​

헬퍼 함수(Helper Function)​

문제​

풀이​

정리​