Recurrent Relation(재귀 관계)
알고리즘에서 특정한 패턴이나 규칙에 따라 값을 반복적으로 계산하는 방법을 나타내는 수학/프로그래밍적 표현. 주로 재귀적인 방법을 사용하여 문제를 해결하거나 순환적인 구조를 다룰 때 사용
예시: 피보나치 수열
피보나치 수열은 재귀 관계를 사용하여 정의된다.
F(n) = F(n-1) + F(n-2)
ex) F(6)를 계산하려면 F(5)과 F(4)를 계산해야 하는 방식임. F(5)도 마찬가지이다. F(4)와 F(3)을 계산..
def fib(n: int) -> int:
if n <= 2:
return 1
else:
return fib(n - 1) + fib(n - 2) // 재귀 호출이 일어나는 부분
result = fib(10)
print(result)
Base Case(기본 사례)
Base case는 재귀적으로 정의된 문제나 함수에서 종료 조건을 정의하는 부분을 나타낸다. Base case는 분할 및 재귀 호출 프로세스를 종료시키는 조건을 제공한다. 그러므로 Base case를 만족하면 재귀적인 호출을 끝내고 결과를 반환하게 된다.
그렇다면 위 피보나치 수열의 Base case는?
n이 0 또는 1일 때이며, F(0)과 F(1)의 값을 직접 반환하게 된다. 이와 같이 Base case를 정의하게 되면 재귀 호출을 더 이상 수행하지 않고 종료하게 된다.
Base case를 정의하지 않으면 무한 루프에 빠질 수 있다. Base case를 명확히 정의함으로써 재귀적인 문제를 해결할 수 있다.
def func(n: int):
if (n <= 0): // Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
return
else:
print("hello")
func(n-1) // Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
result = func(5)
print(result)
Mathmatical Induction(수학적 귀납법)
Base Case(기본 사례): 수학적 귀납법으로 증명하려는 명제가 어떠한 초기값에 대해 참임을 보이는 것으로 귀납법을 시작할 수 있다.
Inductive Hypothesis(귀납 가정): 명제가 어떤 특정 조건 또는 값에 대해 참이라고 가정하는 것
Inductive Step(귀납 단계): 명제가 귀납 가정을 바탕으로 어떤 조건에서 참임을 보이는지를 증명. 귀납 가정을 사용하여 다음 조건에서도 명제가 참임을 보이는 것
0~n까지의 합을 반환하는 함수를 예시로 보자.
def func(n: int):
if (n == 0):
return 0
else:
return n + func(n-1)
- Base case: n = 0인 경우, 0을 반환한다. (참)
- Inductive Hypothesis: 임의의 양의 정수 k에 대해 n<k인 경우 0에서부터 n까지의 합을 올바르게 계산해서 반환한다고 가정
- Inductive Step: n=k인 경우를 고려. func은 먼저 fun(k-1)을 호출하는데 2번의 가정에 의해서 0에서부터 k-1까지의 합이 올바르게 계산되어 반환된다. 메서드 func은 그 값에 n을 더하여 반환한다. 따라서 메서드 func은 0부터 k까지의 합을 올바르게 계산하여 반환한다. (즉, k일 경우에도 성립한다라는 것을 증명함)
수학적 귀납법은 반복적인 패턴을 갖는 명제나 정리의 참을 증명하고, 알고리즘의 정확성을 입증하는 데에 사용된다.
