[Python] 반복과 재귀

• 반복과 재귀의 비교

 

• 2^k 연산에 대한 재귀와 반복

# 재귀 Recursion
def Power_of_2R(k):
    if k == 0:
        return 1
    else:
        return 2 * Power_of_2R(k-1)

print(Power_of_2R(5)) # 32

# 반복 Iteration
def Power_of_2I(k):
    i = 0
    power = 1
    while i < k:
        power = power * 2
        i += 1
    return power

print(Power_of_2I(5)) # 32

 

• 선택 정렬 함수(Selection Sort)를 재귀적 알고리즘으로 작성
  • 범위 내 가장 작은 값과 맨 앞 값 자리 바꾸기 

N = 5
arr = [4,2,1,5,3]

# 인덱스 이동하기
def sort(arr,idx,N):
    # idx 번째 자리에 들어갈 요소 찾아 idx번째 요소랑 자리 바꿔주기
    if idx >= N:
        print(arr)
        print('끝')
        return
    # print(arr[idx],end = ' ')
    # idx 포함 뒤쪽에 있는 원소 중 제일 작은 값 찾기
    min_idx = idx
    for i in range(idx,N):
        if arr[min_idx] > arr[i]:
            min_idx = i
    arr[min_idx], arr[idx] = arr[idx], arr[min_idx]
    sort(arr,idx+1,N)
sort(arr,0,N)