[알고리즘] 재귀적 vs 귀납적

재귀적(recursive) vs 귀납적(inductive) 

수학을 전공한 저에게도 이 용어 자체가 크게 와닿지 않았기 때문에 이해 가기 어렵다면 정상입니다..ㅎㅎ

 

재귀적(Recursive)

함수나 알고리즘이 자기 자신을 호출하여 문제를 해결하는 방식

 

파이썬 코드로 이해하기 쉽게 설명드릴게요.

아래의 코드에서 함수 factorial_recursive 는 자기 자신을 호출하여 n이 1 이하일때 재귀 호출을 멈추도록

기본 조건을 설정하고 있다. 

# 재귀적 함수 예시: 팩토리얼 계산
def factorial_recursive(n):
    # 기본 조건: n이 1 이하일 때 1을 반환
    if n <= 1:
        return 1
    else:
        # 자기 자신을 호출하여 재귀적으로 팩토리얼 계산
        return n * factorial_recursive(n - 1)

# 팩토리얼 계산 예시
result = factorial_recursive(5)
print("5의 팩토리얼은:", result)

 

귀납적(Inducive)

수학적 증명에서 주어진 명제가 일정한 규칙에 따라 기본조건에서 시작하여 모든 경우에 대하여 참임을 증명하는 방법

 

귀납적 추론은 주로 수학적인 증명시 사용된다. (따라서 이는 기본단계에서 시작되며 코드적으로 표현되기 보다 개념적인 측면으로 이해해야함)

 

예를들여,

모든 자연수 n 에 대하여 1부터 n까지 합을 구하는 공식을 증명하는 경우, 

 

n=1일때 참이고, n=k 일때 참이라고 가정

n=k+1 일때도 성립함을 증명함으로 전체가 모두 성립함을 보일때 사용된다. 

 

재귀적인 알고리즘은 문제를 해결하는 방법

귀납적 추론은 증명 방법중 하나이다.

# 귀납적 증명 설명 (주석)

귀납적 증명(Inductive Proof)
1. 기본 단계(Base Case): 주어진 명제가 처음 몇 개의 경우에 대해 참임을 보인다
2. 귀납적 가정(Inductive Hypothesis): 명제가 k에 대해서 참이라고 가정한다
3. 귀납적 단계(Inductive Step): k+1에 대해서 명제가 참임을 보인다
4. 따라서, 모든 경우에 대해 명제가 참이라는 것을 증명한다

 

따라서 두 용어는 다른 맥락에서 사용되므로 혼돈하지 말자!