[Python] 4장 재귀와 반복 : 자연수 계산

 

 

1. 재귀함수 vs 꼬리재귀

 

재귀 (recursive) 함수	꼬리 재귀 (tail recursion) 함수
계산한 결과에다 더할 수를 기억 -> 재귀 호출의 횟수만큼 저장 공간을 사용	더 이상 기억해둘 것이 없음 (답을 누적) -> 공간이 필요 없음 (공간 절약)
return n + sima(n-1) 이용	return loop(counter, accumulator) 이용

 

 

+) 지역함수를 이용한 캡슐화의 장점은 ??

 

 

 

 

 

 

 

 

 

 

 

2. 재귀 함수 vs while 루프

 

재귀 함수	while 루프
하향식 (Top-down)	상향식 (Bottom-up)
실행 논리를 직관적으로 표현 가능 BUT, 공간 효율이 떨어짐	꼬리 재귀 or while 루프같은 상향식은 공간 절약 가능

 

 

 

 

 

 

 

 

 

 

3. 재귀 vs 꼬리 재귀 vs while 루프 실습  :  sumrange(m,n)    # m부터 n 까지의 합

 

재귀버전

def sumrange(m,n):
    if m <= n:
        return m + sumrange(m+1, n)
    else:
        return 0

 

 

꼬리 재귀 버전

def sumrange(m,n):
    def loop(m, total):
        if m <= n:
            return loop(m+1, m + total)
        else:
            return total
    return loop(m, 0)

 

 

while 루프 버전

def sumrange(m,n):
    total = 0

    while m <= n:
        total += m
        m += 1

    return total

,

 

 

 

 

 

 

 

 

 

4. 분할정복 알고리즘 (divide-and-conquer)

 

 

거듭제곱의 분할정복

 

 

 

 재귀 버전

def power(b,n):
    if n > 0:
        return b * power(b, n-1)
    else:
        return 1

 

 

 

분할정복 알고리즘 재귀 버전

def power(b,n):
    if n > 0:
        if n % 2 == 0:
            return power(b*b, n//2)
        else:
            return b * power(b, n-1)
    else:
        return 1

실행 추적

 

-> power(2, 7)

-> 2 * power(2, 6)

-> 2 * power(4, 3)

-> 2 * 4 * power(4, 2)

-> 2 * 4 * power(16, 1)

-> 2 * 4 * 16 * power(16, 0)

-> 2 * 4 * 16 * 1

-> 2 * 64

-> 128

 

 

 

분할정복 알고리즘 꼬리재귀 버전

def power(b, n):
    def loop(b, n, prod):
        if n > 0:
            if n % 2 == 0:
                return loop(b*b, n//2, prod)
            else:
                return loop(b, n-1, b*prod)
        else:
            return prod

    return loop(b,n,1)

 

 

 

 

 

 

 

 

 

 

 

5. 최대공약수 (greatest common divisor) : 유클리드, 분할정복 알고리즘

 

 

 

최대공약수 gcd()

>>> from math import gcd
>>> gcd(48,18)
6
>>> gcd(18, 48)
6

 

 

 

 

 

5-1. 유클리드 알고리즘

 

 

 

유클리드 알고리즘 재귀식

유클리드 알고리즘 - 꼬리 재귀 버전

# 유클리드 알고리즘
def gcd(m, n):
    if n != 0:
        return gcd(n, m%n)
    else:
        return m

print(gcd(48,18))   #6
print(gcd(0,11))    #11
print(gcd(18, 57))  #3

 

 

유클리드 알고리즘 - while 루프 버전

# while 루프 버전 
def gcd(m, n):
    while n != 0:
        m, n = n, m%n
    return m



print(gcd(48,18))   #6
print(gcd(0,11))    #11
print(gcd(18, 57))  #3

 

 

 

 

 

 

 

 

5-2. 분할정복 알고리즘

 

 

분할정복 알고리즘 - 재귀 버전

def even(n):
    return n % 2 == 0

def odd(n):
    return n % 2 == 1



def gcd(m, n):
    if m != 0 and n != 0:
        if even(m) and even(n):  # m, n 짝수일 때
            return 2 * gcd(m//2, n//2)
        elif even(m) and odd(n):  # m 짝수, n 홀수일 때
            return gcd(m//2, n)
        elif ood(m) and even(n):  # m홀수, n 짝수일 때
            return gcd(m, n//2)
        elif m <= n:              # 둘 다 홀수일 때
            return gcd(m, (n-m)//2)
        else:
            return gcd(n, (m-n)//2)

    else:
        if m == 0:
            return n
        else:
            return m

 

 

 

 

분할정복 알고리즘 - 꼬리재귀 버전

def even(n):
    return n % 2 == 0

def odd(n):
    return n % 2 == 1

def gcd(m, n):
    def loop(m, n, k):
        if m != 0 and n != 0:
            if even(m) and even(n):
                return loop(m//2, n//2, 2 * k)
            elif even(m) and odd(n):
                return loop(m//2, n, k)
            elif odd(m) and even(n):
                return loop(m, n//2, k)
            elif m <= n:
                return loop(m, (n-m)//2, k)
            else:
                return loop(n, (m-n)//2, k)
        else:
            if m == 0:
                return n * k
            else:       # n == 0
                return m * k
    return loop(m, n, 1)


print(gcd(18,48))
                

 

 

 

 

분할정복 알고리즘 - while 루프 버전

def gcd(m, n):
    k = 1
    while m != 0 and n != 0:
        if even(m) and even(n):
            m, n, k = m//2, n//2, 2* k
        elif even(m) and odd(n):
            m = m//2
        elif odd(m) and even(n):
            n = n//2
        elif m <= n:
            n = (n-m)//2
        else:
            m, n = n, (m-n)//2

    if m == 0:
        return n * k
    else:     # n == 0
        return m * k


print(gcd(18,48))