[전공 서적 번역] Recursion

" Data Structures & Algorithms in Python 시리즈 -1"

Lecture 4 : Recursion

Lecture의 번역 정리본은 정리해서 올라올 예정이다.
재귀의 경우, 해설이 필요하여 4장의 경우 연습문제 해설을 함께 올렸다.

코드는 다음 링크에서 확인 가능하다.

메인 예제 복습) English Ruler

def draw_line(tick_length, tick_label=''):
    line = '-' * tick_length
    if tick_label:
        line += ' ' + tick_label
    print(line)

def draw_interval(center_length):
    if center_length > 0:
        draw_interval(center_length - 1)
        draw_line(center_length)
        draw_interval(center_length - 1)

def draw_ruler(num_inches, major_length):
    draw_line(major_length, "0")
    for j in range(1, 1+num_inches):
        draw_interval(major_length - 1)
        draw_line(major_length, str(j))

코드 설명

• 내가 위 (b)와 같은 그림의 자를 그리고 싶다고 생각을 해보자. 그냥 무식하게 5 1 2 1 3 1 2 1… 이런식으로 라인을 입력값으로 받아서 출력할 수도 있을 것이다. 하지만 자세히 구조를 보면, 2개씩 갈라지는 구조로 패턴이 있는 것이 눈에 띤다. 이는 two call recursion 문제를 접근해볼 수 있음을 뜻한다.
• 그럼 어떻게 순서를 따라야하는가? 1이 그릴 수 있는 최소단위라고 생각하면, 위 그림 기준으로 5에서 4를 4에서 3을 3에서 2를 2에서 1을 호출한다고 생각하는게 맞아보인다. 물론 이건 한 블럭을 기준으로 하니 또 다른 쪽도 같은 과정이 반복된다고 생각한다. (그려놓은 오른쪽 빨,파,검 선) 이를 위해선 0에선 call이 종료되는 함수가 필요할 것이다.
• 재귀함수는 “그리는 행동”을 반복 할 것이다. 아래의 그림이 (3,3) 입력에 대한 결과인데, 다음과 같이 블록을 나눠서 보면 코드화하기 편하다. 파란색이 draw_interval(2)가 그리는 하나의 조각이다. 그 안에서 그려지는 순서는 recursion 트리를 그려보도록 하자.

→ (a) 는 3이 두 번 호출된 것이고, (b)는 4가 한번 호출된 것이다. (위, 아래 줄긋기 제외.)

Excercises 4 풀이

4.1 Describe a recursive algorithm for finding the maximum element in a sequence, S, of n elements. What is your running time and space usage?

def find_max(arr, index):
    if index == len(arr) - 1 : return arr[index]
    return max(arr[index], find_max(arr, index+1))

• 큰 원소를 찾기 위해서 일반적으로 시퀀스 길이만큼의 탐색을 진행해야한다. 그리고 재귀적으로 구현하더라도 배열에서 가장 큰 원소를 찾기 위해서 O(n) 만큼의 시간이 필요하다. 위 코드의 경우 시간복잡도는 O(n)이 걸리게되고, 마지막 n번째 원소까지 호출했을 때, 열려있는 메모리 공간 또한 O(n)이 된다.

4.3 Draw the recursion trace for the computation of power (2,18), using the repeated squaring algorithm, as implemented in Code Fragment 4.12.

• 처음 접근 한 방법.
  • def main(a,b): return a**b
  • 이 과정은 aa … aa 과정이 생략되어있다.
    • 그러니까 a를 b번이나 곱해야한다는 것이다. 곱하는 과정 또한 loop문으로 생각하면 O(b) 가 든다.
    • 근데, 이걸 이제 재귀적으로 구현해보면….

def power(base, top):
    if top == 0:
        return 1
    return base * power(base, top-1)

• recursion trace를 해보면, $2^{18} = 2* 2^{17}$ 로 쪼개어 코드 작성이 가능하다.

• 위 문제를 squaring technique로 더 빠르게 풀어보자.

  • 포인트 - partial * partial 로 쪼개서 재귀적으로 call 할 수 있는 것이다.

def power(base, top):
    # writing code
	  if top == 0:
        return 1
    partial = power(base, top//2) # lower bound
    result = partial * partial
    if top % 2 == 1:
        return result *= base # odd
    return reuslt

• 위와 같은 그림 처럼, 재귀적으로 호출이 일어날 것이다.

4.5 Draw the recursion trace for the execution of function PuzzleSolve(3,S,U)
(Code Fragment 4.14), where S is empty and U = {a,b,c,d}.

• p. 197의 함수 자체는 U의 집합의 모든 원소에 대해서 중복 없이 k 길이를 가진 문자열을 반환하는 것이다.

• Recursion trace

pass

4.7 Describe a recursive function for converting a string of digits into the integer it represents. For example, “13531” represents the integer 13,531.

# recursion 생각 안했을 때.
def str2int(string:str):
    cnt=0
    for digit, i in enumerate(map(int, string[::-1])):
        cnt += ((10**digit) * i)
    return cnt

# recursion 풀이.
def str2int(string, length):
    # length = len(string)
    stand = len(string)
    if length <= 0:
        return 0

    first = string[stand-length] 
    cnt = str2int(string, length-1)
    cnt += int(first) * (10**(length-1))
    return cnt

• 문자열을 수치형 자료로 바꿀 때, 재귀를 이용하여 코드를 작성하였다. 손으로 풀어서 써보면 문자의 길이와 10의 차수와의 관계 그리고 계수와의 패턴이 나타난다. 재귀적으로 호출하며 하나씩 수를 늘려가면서 더해준다.

문제 추가

• 재귀 방법으로 구현한 병합 정렬에 대한 코드이다.
  추가로 공부하기 위해서 구현된 여러 병합 정렬 코드들을 비교하였는데,
  대부분 많이 접근하고 있는 슬라이싱 후 호출의 경우, 파이썬 리스트 객체가 다시 만들어지는 구조기 때문에 메모리 공간이 많이 든다. (Lecture 5 참고)
  따라서, 병합 정렬 구현 중 메모리 공간을 적게 쓰는 것으로 코드를 찾고, 이를 도식화하여 공부해보았다.

https://www.daleseo.com/sort-merge/ (No slicing version)

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

→ Time usage : SlogS : S* log S
→ Space usage : 1호출 시 필요한 공간의 정도? S

이를 도식화하면 아래와 같이 호출이 일어나게 된다. 맞다. 복잡하다. 그래서 그림으로 한번 그려보면 이해가 수월해진다.