11 재귀

11.1 재귀 함수

11.1.1 재귀 함수란?

재귀 함수(recursion function): 조건부로 자신을 부르는 함수

 

일반 함수 호출

재귀 함수 실행 예시

 

11.1.2 팩토리얼 함수

팩토리얼 함수의 재귀적인 정의

적절히 정의된 모든 재귀 함수는 적어도 하나의 기본 케이스를 가져야 하며, 원래 문제의 해가 재귀적으로 해결된 하위 문제의 해에서 도출될 수 있도록 문제를 기본 케이스를 향해 작동하는 하위 문제로 재정의해야 한다.

factorial(4) = 4 * 3 * 2 * 1 = 24

factorial(n) = n * (n - 1) * (n - 2) * . . . 1 = n * factorial(n-1)

 

팩토리얼 함수의 완벽한 정의

factorial(n) = 1, if n = 0
                    = n * factorial(n - 1), otherwise

 

재귀적 함수의 요구조건

1. 기본 케이스가 하나 이상 있어야 한다(추가적인 재귀 분석 없이 해결 방법을 알 수 있는 문제 인스턴스).
2. 베이스 케이스가 아닌 문제는 원래의 문제와 유사한 종류의 문제인 하위 문제로 분해되어 베이스 케이스를 향해 작동한다.
3. 이것은 재귀적으로 해결된 하위 문제의 해결책으로부터 원래 문제의 해결책을 도출하는 방법이다.

 

팩토리얼 함수는 세 가지 요구조건을 모두 충족하므로 재귀적 함수이다.

 

재귀적인 팩토리얼 함수 실행

패토리얼 함수는 재귀적 함수의 예로 자주 사용되지만 반복을 사용하도록 구현하면 함수를 더 효율적으로 실행할 수 있다.

 

def factorial(n):
	if n == 0:
    	return 1
    else:
    	return n * factorial(n-1)

팩토리얼 재귀적 인스턴스 호출

11.2 재귀적 문제 해결

11.2.1 재귀적으로 생각하기

재귀의 힘(power of recursion)은 개념적으로 우아한 문제 해결 수단을 제공한다는 것이다.

예시)

factorial(n)을 n과 factorial(n-1)이라는 2개의 subproblem으로 나눌 수 있다. 

factorial(n) = n * factorial(n-1)

11.2.2 병합 정렬 재귀적 알고리즘

리스트 정렬하기 문제 분해하기

문제를 분해할 때는 종종 문제를 같은 크기의 하위 문제로 분해하는 것이 가장 효과적이다.

두 개의 하위 리스트로 정렬한 이후

두 정렬된 리스트를 병합하는 과정

 

병합 정렬(merge sort)의 알고리즘의 완벽한 단계

1. 목록을 두 개의 하위 목록으로 나눈다.
2. 각 하위 목록을 정렬한다.
3. 정렬된 하위 목록을 하나의 정렬된 목록으로 병합한다.

 

재귀적 문제 해결 예시 (병합 정렬)

11.2.3 적용하자- 병합 정렬 실행

재귀 함수 mergesort

def mergesort(lst):
	
    if len(lst) == 1:
    	return lst
    
    sublist1 = lst[0:len(lst) // 2]
    sublist2 = lst[len(lst) // 2: len(lst)]
    
    sorted_sublist1 = mergesort(sublist1)
    sorted_sublist2 = mergesort(sublist2)
    
    return merge(sorted_sublist1, sorted_sublist2)

def merge(lst1, lst2);
	
    merged_list = []
    
    i = 0
    k = 0
    
    while i != len(lst1) and k != len(lst2):
    	if lst1[i] < lst2[k]:
        	merged_list.append(lst1[i])
            i = i + 1
        else:
        	merged_list.append(lst2[k])
            k = k + 1
    
    
    if i < len(lst1):
    	for loc in range(i, len(lst1)):
        	merged_list.append(lst1[loc])
    elif k < len(lst2):
    	for loc in range(k, len(lst2)):
        	merged_list.append(lst2[loc])
    
    return merged_list

mergesort -> 분해하는 과정 거친 후  merge함수를 return한다.

merge -> 정렬하면서 병합하는 과정

11.3 반복 대 재귀

재귀를 사용하여 계산할 수 있는 것은 무엇이든 반복을 사용하여 계산할 수 있으며, 그 반대도 마찬가지이다.

일반적으로 재귀 함수는 등가 반복 접근법보다 실행하는 데 더 많은 시간이 걸리므로

따라서 비슷한 프로그래밍 노력으로 재귀적 및 반복적으로 문제를 풀 수 있을 때는

일반적으로 반복 접근법을 사용하는 것이 가장 좋다. 

반면에 어떤 문제들은 반복적으로 푸는 것이 매우 어렵고, 재귀적으로 푸는 것은 거의 사소하다.

이때가 재귀가 가장 효과적으로 사용되는 때이다.