アルゴリズム-再帰アルゴリズム

再帰アルゴリズム

# 재귀 알고리즘
def recursion(num):
    if num > 0 :
        print('*'*num)
        return recursion(num-1)
    else:
        return 1

ハノイタワー

# 하노이 탑 이동 순서 출력
def hanoi(start, to, end, n):
    if n == 1:
        print(start, end)
    else:
        hanoi(start, end, to, n-1)
        print(start, end)
        hanoi(to, start, end, n-1)

配置

1.連結ソート

# 병합 정렬
def mSort(ns):
    if len(ns) < 2:
        return ns
    midIdx = len(ns) // 2
    leftNums = mSort(ns[:midIdx])
    rightNums = mSort(ns[midIdx:])

    mergeNums = []
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1
    
    mergeNums = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums

nums = [8, 1, 4, 3 ,2, 5, 10, 6]
print('mSort(nums) : {}'.format(mSort(nums)))

2.クイックソート

# 퀵 정렬
def qSort(ns):
    if len(ns) < 2 :
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []
    sameNums = []
    bigNums = []

    for n in ns:
        if n < midVal:
            smallNums.append(n)
        elif n == midVal:
            sameNums.append(n)
        else:
            bigNums.append(n)
        
    return qSort(smallNums) + sameNums + qSort(bigNums)

nums = [8, 1, 4, 3, 2, 5, 10, 6]
print('not sorted nums : {}'.format(nums))
print('sorted nums : {}'.format(qSort(nums)))