[1. 순환(Recursion)] 순환 알고리즘 설계

모든 Recursion은 Iterative 함수로 표현이 가능하다. 그 역도 성립한다. 두개를 비교해보면 Recursion을 어떻게 설계하는게 좋을지 알 수가 있다. 

 

1. Recursion 설계 포인트

1) 임시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

2) 적어도 하나의 base case(순환이 종료되는 시점)이 존재해야 하며, 모든 recursive case가 base case로 수렴해야 한다.

 

Recursion 설계 예시

1) 이진탐색

- Iterative version

def binary_search_iterative(data, target):
	n = len(data)
    assert n > 0
    
    begin = 0
    end = n-1
    
    while bigin <= end:
    	middle = int((begin+end)/2)
        if data[middle] == target:
        	return middle
        elif target < data[middle]:
        	end = middle-1
        else:
        	begin = middle+1
        
    return None

 

- Recursion version

def binary_search_recursive(data, target, begin, end):
	if begin>end:
    	return None
    else:
    	middle = int((begin+end)/2)
        if target == data[middle]:
        	return middle
        elif target > data[middle]:
        	begin = middle+1
            return binary_search_recursive(data, target, begin, end)
        else:
        	end = middle-1
            return binary_search_recursive(data, target, begin, end)
            

 

두 개를 비교해보면 resursive 알고리즘을 만들기 위해서 매개변수로 begin, end를 추가해줬다. 이는 iterative 알고리즘에서는 함수 내부적으로만 사용되는 개념이었는데 이를 명시적으로 사용함으로써 recursive하게 호출할 수 있다.

 

 

 

 

[References]

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