2.6 Recursion

개념

재귀는 함수가 실행 중에 자기 자신을 호출하는 방식입니다. 함수를 다시 호출하면 새로운 호출이 시작되고, 기존 호출은 그 호출이 끝난 뒤 이어서 실행됩니다.

재귀 함수의 구성

재귀 함수에는 다음 두 가지를 정해야 합니다.

1. 종료 조건: 더 호출할 필요 없이 현재 호출을 끝낼 수 있는 조건입니다.
2. 재귀 호출: 다음 호출에 전달할 입력을 정하고 자기 자신을 호출합니다. 호출을 반복할수록 종료 조건에 가까워져야 합니다.

팩토리얼을 재귀로 계산하기

팩토리얼 $N!$은 $1$부터 $N$까지의 정수를 모두 곱한 값입니다. 예를 들어 $3!=3\times2\times1=6$이며, $0!=1$로 정의합니다.

$N$의 팩토리얼을 구하는 함수를 $F(N)$이라고 하겠습니다. $N\ge1$이면 $N$을 제외한 나머지 곱은 $(N-1)!$이므로, $F(N)=N\times F(N-1)$로 계산할 수 있습니다.

입력이 $3$이면 다음 호출의 입력은 $2,1,0$으로 줄어듭니다. $0$을 받은 호출에서 종료 조건을 만족하므로 호출이 멈춥니다.

호출이 시작되는 순서

$F(3)$을 실행하면 다음 순서로 호출이 시작됩니다.

각 호출의 매개변수와 지역 변수는 따로 보관됩니다. $F(3)$의 입력은 $3$으로 유지되고, 새로 시작한 $F(2)$는 입력 $2$로 실행됩니다.

호출이 끝나고 돌아오는 순서

$F(0)$이 반환한 값은 자신을 호출했던 $F(1)$로 전달됩니다. $F(1)$은 기다리던 곱셈을 수행한 뒤 결과를 $F(2)$에 반환합니다.

종료 조건을 만족하면 현재 호출 하나가 끝납니다. 그 전에 시작한 호출들은 각각 돌아온 위치부터 실행을 이어 갑니다. 따라서 호출은 $F(3),F(2),F(1),F(0)$ 순서로 시작하고, 반환은 $F(0),F(1),F(2),F(3)$ 순서로 이루어집니다.

호출 깊이와 복잡도

실행을 마치지 않은 호출의 정보는 호출 스택에 저장됩니다. $F(3)$에서 시작하여 $F(0)$을 실행하는 시점에는 네 호출이 모두 남아 있습니다. 호출이 깊어질수록 필요한 스택 공간도 늘어나므로 입력의 최댓값에서 호출 깊이를 확인해야 합니다. 사용할 수 있는 스택 공간과 재귀 깊이 제한은 실행 환경에 따라 다릅니다.

팩토리얼 계산에서는 $N$부터 $0$까지 총 $N+1$번 호출하고, 각 호출에서 상수 번의 연산을 수행합니다. 동시에 남아 있는 호출도 최대 $N+1$개입니다.

예제

문제

정수 $N$이 주어진다. $N!$을 구하여라. $0!=1$이다.

입력

첫째 줄에 정수 $N$이 주어진다. $0\le N\le10$이다.

출력

$N!$을 출력한다.