재귀란?
ko.khanacademy.org
재귀란
위 러시아 인형은 인형속에 인형을 담고 또 인형을 담고, 결국 인형이 너무 작아져서 담지 못할때까지 담습니다.
위 예시와 알고리즘과의 연관 관계는 '인형을 작아져서 담지 못할때까지 담는다'에 있습니다. 알고리즘에서 어떤 문제를 해결하기 위해서 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 방식이 위 예시와 닮아있습니다. 계속해서 더 작은 경우를 해결하다보면 결국 문제가 간단해지고 쉽게 풀수있습니다. 이러한 테크닉을 '재귀'라 합니다.
반복문 팩토리얼 함수
우선 팩토리얼 함수를 반복문을 통해서 구해보겠습니다.
static int Factorial(int n)
{
var result = 1;
for (int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}팩토리은 만약 5!일 경우 5*4*3*2*1란 식이 나옵니다. 이를 1부터 차례대로 올라가면 1*2*...*n 이 됩니다. 그대로 함수에 입력해주면 됩니다.
재귀 팩토리얼의 과정
그럼 팩토리얼을 재귀를 통해 구해보겠습니다.
먼저 다시한번 n!를 어떻게 구할수있을까요. n*(n-1)*(n-2)*...*2*1로 표현이 가능합니다. 이를 다른 방식으로 표현하면
n! = n*(n-1)!라고 할 수 있습니다. 여기서 n!를 (n-1)!로 표현했음을 주목해봅니다.
다시 정리하면, (n-1)!을 계산한 결과와 n을 곱하면 n!를 구할수있다는 의미입니다. n의 팩토리얼 함수는 n-1 팩토리얼 함수를 계산해서 구할 수 있습니다. 여기서 (n-1)!를 계산하는 것은 n!의 하위 문제라고 말합니다
5!을 예를 들어 계산해보겠습니다.
- 5!를 계산하는 하위 문제는 5*4!로 표현할 수 있습니다
- 4!를 계산하는 하위 문제를 해결해야합니다. 이는 4*3! 입니다.
- 3!를 계산하는 하위 문제는 3*2! 입니다.
- 2!는 2*1!로 계산됩니다.
- 1!는 1입니다.
- 0!은 1로 정의되어 있습니다.
- 그렇다면 1! = 1*0! = 1 로 풀이할 수 있습니다.
- 1! = 1이기에 2! = 2*1! = 2로 계산됩니다.
- 2! = 2이기에 3! = 3*2! = 6으로 계산됩니다.
- 3! = 6이기에 4! = 4*3! = 24으로 계산됩니다.
- 4! = 24이기에 5! = 5*4! = 120으로 계산됩니다.
그럼 음이 아닌 정수 n에 대하여 n!을 계산하는 또 다른 방법을 알게 됐습니다.
- n = 0 이면 n! = 1 입니다.
- 그 외에 n은 양수이어야 하며, (n-1)!를 계산하는 하위 문제를 해결하여 그 결과값을 n과 곱합니다. 그리고 n!을 이 곱의 결과값으로 선언합니다.
n!을 이런 식으로 계산하면서 즉석에서 답을 구할 수 있는 첫 번째 조건을 탈출 조건이라 부릅니다. 다른 값에 대한 같은 함수를 계산하는 두 번째 케이스를 재귀 조건이라고 합니다.
재귀 팩토리얼 함수의 구현
앞서 글로서 작성한 내용을 재귀 함수로 구현해보겠습니다.
static int Factorial(int n)
{
//탈출 조건 (base case)
if(n==0)
{
return 1;
}
//재귀 조건 (recursive case)
return n * Factorial(n - 1);
}재귀 함수에서 제일 먼저 적어줘야할것은 탈출 조건입니다. 팩토리얼의 값의 탈출 조건은 n==0일때 즉, 0!일때 값을 1로 반환하는 겁니다.
하지만 여전히 재귀가 감이 잡히질 않습니다. 다음 글에서 재귀 알고리즘을 더 공부해보겠습니다.