분할 정복법(divide and conquer)

• 문제 해결 방법 중에서 가장 유명한 재귀적 알고리즘
• 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법
• 퀵 정렬(quick sort)이나 병합 정렬(merge sort)도 분할 정복 알고리즘이다.

분할 정복 전략은 다음과 같이 동작한다.

1. 기본 단계를 찾는다.
2. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾는다.

재귀로 배열의 합계 구하기

1. 기본단계 : 원소의 개수가 0이면 합계는 0을 반환한다.
2. 재귀단계 : 기본단계가 될 때까지 대상이 되는 배열의 크기를 줄여서 보낸다.

pydef sum(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sum(arr[1:])
 
def main():
    print(sum([1,2,3,4,5]))
 
if __name__ == "__main__":
    main()