재귀 — 작동 원리, 예시, 기저 사례

수학에서 재귀란 함수, 수열, 또는 과정을 같은 아이디어의 더 작은 경우를 이용해 정의하는 것을 뜻합니다. 재귀적 정의가 제대로 작동하려면 기저 사례와, 각 새로운 경우를 그 기저 사례 쪽으로 이동시키는 규칙이 함께 있어야 합니다.

핵심만 말하면 이렇습니다. 더 작은 단계로 가는 규칙이 더 이상 유효한 종료 지점에 도달하지 못하는 순간, 재귀는 쓸모를 잃습니다.

수학에서 재귀의 의미

재귀적 정의는 모든 경우를 하나하나 따로 나열하지 않습니다. 대신 시작점과, 더 작은 경우로부터 더 큰 경우를 만드는 규칙을 제시합니다.

이것은 직접 공식과는 다릅니다. 직접 공식은 입력값으로부터 하나의 식으로 바로 답을 줍니다. 반면 재귀적 정의는 이미 알려진 경우에 도달할 때까지 문제를 단계적으로 줄여 갑니다.

기저 사례는 멈추는 지점입니다. 이것이 없으면 정의는 끝없이 더 작은 경우를 참조하기만 하고 결코 끝나지 않습니다.

또한 기저 사례는 선택한 규칙과도 맞아야 합니다. 재귀 단계가 $n$ 에서 $n-1$ 로 줄어든다면, 허용한 입력 범위 안에서 그 패턴을 따라 실제로 도달할 수 있는 기저 사례가 있어야 합니다.

팩토리얼은 대표적인 재귀적 정의입니다. 정수 $n \ge 0$ 에 대해 팩토리얼을 다음과 같이 정의합니다.

0! = 1

그리고 $n \ge 1$ 일 때,

n! = n(n-1)!

여기서 $0! = 1$ 은 기저 사례이고, $n! = n(n-1)!$ 는 재귀 단계입니다.

$4!$ 를 구하려면 기저 사례가 나올 때까지 계속 줄이면 됩니다.

4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!

이제 기저 사례 $0! = 1$ 을 적용합니다.

4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24

이것이 재귀의 전체 패턴입니다. 더 작은 경우로 줄이고, 기저 사례에 도달한 뒤, 다시 원래 문제까지 값을 계산해 올라갑니다.

재귀는 더 넓은 개념입니다. 점화식은 수열에 대한 재귀 규칙으로, 각 항이 이전 항들에 의존합니다.

예를 들어 피보나치 수열은 각 항이 앞선 항들로 정의되므로 점화식으로 주어집니다. 팩토리얼도 재귀적이지만, 보통은 수열의 점화식이라기보다 함수의 재귀적 정의로 소개됩니다.

기저 사례가 없으면 정의는 끝나지 않습니다.

재귀 단계가 기저 사례 쪽으로 나아가지 않으면, 과정이 무한히 반복되거나 어떤 입력에서는 정의되지 않을 수 있습니다.

팩토리얼 예시에서 규칙 $n! = n(n-1)!$ 는 $n \ge 1$ 일 때 사용합니다. 이 조건은 중요합니다. 이것이 없으면 원래 의도하지 않은 곳에도 그 규칙을 적용하려 할 수 있습니다.

재귀는 코드보다 훨씬 이전부터 수학에 등장했습니다. 더 작은 경우를 참조해 함수, 수열, 집합을 정의하는 방법입니다. 그리고 그런 재귀적 정의에 대한 명제를 증명할 때는 수학적 귀납법이 자주 사용됩니다.

문제가 자기 자신과 같은 형태의 더 작은 문제들로 자연스럽게 나뉠 때 재귀는 유용합니다. 팩토리얼, 피보나치형 수열, 재귀적으로 정의된 집합, 그리고 많은 알고리즘에서 이를 볼 수 있습니다.

특히 더 작은 경우가 원래 문제와 같은 구조를 가질 때 도움이 됩니다. 더 작은 경우가 사실 같은 종류의 문제가 아니라면, 재귀는 보통 적절한 도구가 아닙니다.

다음 두 가지를 물어보세요.

둘 중 하나라도 아니오라면, 그 정의는 수정이 필요합니다.

다음과 같이 수열을 정의해 봅시다.

a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2

그다음 $a_2$ , $a_3$ , $a_4$ 를 구해 보세요. 새로운 상황에서 기저 사례와 재귀 단계를 찾아보는 간단한 연습이 됩니다.

문제를 올리면 검증된 단계별 풀이를 몇 초 만에 받을 수 있습니다.