재귀함수. 마스터

https://data-marketing-bk.tistory.com/entry/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%9D%98-%EC%99%84%EB%B2%BD-%EC%9D%B4%ED%95%B4-%EB%B0%8F-%EA%B5%AC%ED%98%84Recursive-Function

재귀함수의 완벽 이해 및 구현(Recursive Function)

 

if 조건:

      return 재귀

else:

     return base

 

 

예시 문제: merge sort

%% 실수한 부분: elif list1[i]>= list2[j]을 '='부분 빼고 돌려서 =인 경우가 둥둥 뜸

 

def merge(list1, list2):
    # 지난 실습의 코드를 여기에 붙여 넣으세요
    i = 0
    j = 0
    tmp_list = []
    while i < len(list1) and j < len(list2):
        if list1[i]<list2[j]:
            tmp_list.append(list1[i])
            i +=1
        elif list1[i]>= list2[j]:
            tmp_list.append(list2[j])
            j +=1
    if i == len(list1):
        tmp_list += list2[j:]
    elif j == len(list2):
        tmp_list += list1[i:]
    return tmp_list
    
# 합병 정렬
def merge_sort(my_list):
    # 여기에 코드를 작성하세요
    if len(my_list)<2:
        return my_list
    else:
        left_list = my_list[:len(my_list)//2]
        left_list = merge_sort(left_list)
        right_list = my_list[len(my_list)//2:]
        right_list = merge_sort(right_list)
        return merge(left_list, right_list)
    
# 테스트 코드
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))