[1. 순환(Recursion)] 개념 및 예제

1. 순환 알고리즘 개념

Recursion이란? 자기 자신을 호출하는 함수

def func(o):
	...
    func(o2)
    ...

 

다음은 recursion을 적용하여 $0 \cdots N$의 정수 배열의 합을 구하는 함수를 구현한 것이다.

def array_sum(N):
	if N == 0:
    	return 0
    else:
    	return N + array_sum(N-1)

 

Recursion은 무한루프에 빠지기 쉽다. 때문에 다음 조건은 거의 필수적이다

• base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.(terminal condition 등)
• recursive case: recursion을 반복하면서 base case로 수렴해야 한다

 

Recursion은 점화식처럼 생각할 수 있다. 위 예시에서 $N$ + array_sum($N$) 부분은 '$N$이 0보다 크다면 $0 \cdots N$의 합은 $0 \cdots N-1$까지의 합에 $N$을 더한 것이다'라고 생각할 수 있다. 즉 점화식에서 처럼 현재 항과 이전 항과의 관계가 한 수식에 표현되어 있는 것이다. 

$$T(\theta_{N}) = f(T(\theta_{N-1}))  $$

 

 

2. 순환 알고리즘 예제들

1) 팩토리얼(Factorial) 계산

- $0! = 0$

- $N! = N \times (N-1)! (N>0)$

def factorial(N):
	if N==0:
    	return 0  # base case 
    else:
    	return N * factorial(N-1)  # recursive case

 

2) 지수(power) 계산

- $X^{0} = 1$

- $X^{N} = X*X^{N-1}, (N>0)$

def power(x, N):
	if N==0:
    	return 1  # base case
    else:
    	return x * power(x, N-1)  # recursive case
    	

 

3) 피보나치 수(Fibonacci number) 계산 

- $f_{0}=0$, $f_{1}=1$

- $f_{N} = f_{N-1} + f_{N-2}, (N>1)$

def fibonacci(N):
	if N < 2:
    	return N  # base case
    else:
    	return fibonacci(N-1) + fibonacci(N-2)  # recursive case

 

4) 최대공약수 계산(Euclid Method) 계산 

- $m\geq n$인 두 양의 정수 $m,n$에 대하여 $m$이 $n$의 배수이면 $gcd(m,n)=n$이고, 그렇지 않다면 $gcd(m,n) = gcd(n, m%n)$이다.

def gcd(m,n):
	assert m>n
    if m%n == 0:  # base case
    	return n
    else:  
    	return gcd(n, m%n)  # recursive case

 

 

 

[References]

• 권오흠 교수, 알고리즘(강의 링크)