[1. 순환(Recursion)] Recursive하게 생각하기

순환하는 알고리즘을 익숙하게 받아들이기는 쉽지가 않은 것 같다. 함수의 출력물이 함수라고 생각되기 때문이다. 순환 알고리즘을 생각하기 위해서는 '바로 직전 스텝에서의 함수의 출력물을 사용한다', 또는 '현재 스텝에서의 함수의 출력물을 바로 다음 스텝에서 사용한다'는 방식의 사고가 필요하다. 즉 brute force처럼 스텝별로 탐색하도록 설계하는 것이다. 

 

(1) 문자열의 길이 계산

def string_length(string):
	assert type(string) == str
    if string=='':  # base case
    	return 0
    else:
    	return 1 + string_length(string[1:])  # recursive case

 

(2) 문자열의 프린트

def print_forward(string):
	assert type(string) == str
    if string == '':  # base case
    	return None
    else:
    	print('%s' % string[0])
        print_forward(string[1:])  # recursive case

 

(3) 문자열을 뒤집어 프린트

def print_backward(string):
	assert type(string) == str
    if string == '':  # base case
    	return None
    else:
    	print_backward(string[1:])  # recursive case
        print('%s' %s string([0])  # --위 예제에서 print 순서만 다름--

 

 

(4) 순차 탐색

- $data[0] \cdots data[N-1]$의 배열에서의 끝에서부터 target을 검색함

- 존재하면 첫번째 결과의 index를 반환함. 존재하지 않으면 None 반환

 

끝에서부터 탐색하는 이유는 N을 매개변수로 주면서 최대값이 정해져있기 때문에 처음부터 탐색하는 것 보다 base case에 대한 조건을 주기가 좀 더 수월하다

def search(data, N, target):
	# data: 개수가 N개인 배열
    # N: 배열의 item 수
    if N < 0:  # base case
    	return None
    elif target == data[N-1]:  # answer case
    	return N-1
    else:
    	return search(data, N-1, target)  # recursive case
    	

 

 

(5) 최대값 찾기

- 배열 $data[0] \cdots data[N-1]$ 에서 최대값을 찾기

def find_max(N, data):
	# N: 배열 data의 item 총 개수
	if N < 0:
    	return 0  # base case
    else:
    	return max(data[N-1], find_max(N-1, data))  # recursive case

 

 

(6) 정수를 2진수로 변환하여 출력

- 입력 정수의 몫과 나머지를 구하는 과정을 반복적으로 수행

- 반복되는 과정에서 나머지를 출력

 

def print_binary(N):
	if N < 2:
    	print('%d'%N)  # base case
    else:
    	print_binary(N//2)  # recursive case
        print('%d'%(N%2))

 

 

(7) Disjoint Sets

- 배열 $A= [A[0] \cdots A[M-1]]$과 배열 $B= [B[0] \cdots B[M-1]]$에 정수들이 정렬되어 저장되어 있을 때 두 배열의 정수들이 disjoint한지 검사한다

def is_disjoint(N, A, M, B):
	if (N<0 || M<0):  # base case
    	return True
    elif A[N-1] == B[M-1]:
    	return False
    elif A[N-1] > B[M-1]:
    	is_disjoint(N-1, A, M, B)  # recursive case
    else:
    	is_disjoint(N, A, M-1, B)  # recursive case
        

 

 

 

[References]

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