[04-02] 재귀 호출 - 재귀 함수를 비재귀 함수로

1. 개요 & 알고리즘

재귀 호출은 다음과 같은 이유로 실질적인 사용에 있어서는 배제되는 경우가 많습니다. ("C로 배우는 알고리즘", p.274)

1. 함수 호출에 따른 Context Switching에 시간이나 resource를 사용해야 하므로, 재귀 호출을 사용하지 않는 경우에 비해서 속도가 느립니다.

2. 재귀 호출시 계속 Stack을 사용하게 되므로, 시스템 다운의 우려(혹은 메모리의 과도한 사용)가 있습니다.

재귀 함수를 비재귀 함수로 변경하는 것은 생각보다 쉬운일이 아니지만, 유형별로 확인해 봅니다.

1.1. 재귀 호출이 하나인 경우

For나 While등의 순환문을 이용해서 비재귀 함수를 재구성해 봅니다.

1.2. 재귀 호출이 둘인 경우 1

세 가지로 구분할 수 있습니다. 재귀 호출하는 부분을 제외한 나머지 실제로 작업을 하는 부분을 process() 함수라고 정의한다면, 이 process()가 두 재귀 호출의 앞에 나와 있는가, 아니면 두 재귀 호출의 사이에 있는가, 아니면 두 재귀 호출의 뒤에 있는가하는 세가지입니다.

1.2.1 유형 1 - process()가 두개의 재귀 호출 앞에 있는 경우

recursive(인자 리스트)
{
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        process(인자 리스트)
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.276)

non_recursive(인자 리스트)
{
    /* 스택의 초기화 */
    init_stack()
    push(인자 리스트)
    /* 스택이 비면 끝 */
    while(!is_stack_empty())
    {
        인자 리스트 = pop()
        if(!종료 조건)
        {
            process(인자 리스트)
            push(변경된 인자 1)
            push(변경된 인자 2)
        }
        /* 종료 조건이면 */
        else
        {
            종료 처리
        }
}

1.2.2 유형 2 - process()가 두개의 재귀 호출 가운데 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        process(인자 리스트)
        recursive(변경된 인자 2)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.279~280)

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    int done = 0;
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 = pop()
            process(인자 리스트)
            인자 리스트 = 변화된 인자 2
        }
        else
        {
            done = 1
        }
}

1.2.3 유형 3 - process()가 두개의 재귀 호출 뒤에 있는 경우

recursive(인자 리스트)
{
    지역 변수들
    if (종료 조건)
    {
        종료 처리
    }
    else
    {
        recursive(변경된 인자 1)
        recursive(변경된 인자 2)
        process(인자 리스트)
    }
}

를 아래와 같이 변형합니다. ("C로 배우는 알고리즘", p.282~284)

non_recursive(인자 리스트)
{
    /* 작업을 완료 했은지를 확인하기 위한 Flag */
    int done = 0;
    /* 무한 루프를 방지하기 위한 방책 */
    인자 리스트의 복사본
    /* 스택의 초기화 */
    init_stack()
    while(!done)
    {
        while(!종료 조건)
        {
            push(인자 리스트)
            인자 리스트 = 변화된 인자 1
        }
        종료 처리
        if(!is_stack_empty())
        {
            인자 리스트 복사본 = 인자 리스트
            인자 리스트 = pop()
            if (인자 2로의 변화가 종료 조건이 아니면)
            {
                if(인자 2로의 변화 == 인자 리스트의 복사본)
                {
                    process(인자 리스트)
                }
                else
                {
                    push(인자 리스트)
                    인자 리스트 = 변화된 인자 2
                    break
                }
            }
        }
        else
        {
            process(인자 리스트)
        }
        if(is_stack_empty)
        {
            done = 1
        }
}

2. 동작 코드

이진 나무 타기 함수들을 앞서의 내용에 따라 Python으로 작성했습니다. 함수명 뒤에 _nr이 붙은 함수가 비재귀 함수입니다.

유형 1

def preorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.visit(node)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

def preorder_traverse_nr(self, n):
    stack = []
    node = n
    stack.append(node)
    while len(stack) != 0:
        node = stack.pop()
        if node != self.tail:
            self.visit(node)
            stack.append(node.right)
            stack.append(node.left)

유형 2

def inorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.inorder_traverse(node.left)
        self.visit(node)
        self.inorder_traverse(node.right)

def inorder_traverse_nr(self, n):
    stack = []
    node = n
    done = 0
    while done == 0:
        while node != self.tail:
            stack.append(node)
            node = node.left
        if len(stack) != 0:
            node = stack.pop()
            self.visit(node)
            node = node.right
        else:
            done = 1

유형 3

def postorder_traverse(self, n):
    node = n
    if node != self.tail:
        self.postorder_traverse(node.left)
        self.postorder_traverse(node.right)
        self.visit(node)

def postorder_traverse_nr(self, n):
    stack = []
    node = n
    done = 0
    while done == 0:
        while node != self.tail:
            stack.append(node)
            node = node.left
        while len(stack) != 0:
            t = node
            node = stack.pop()
            if node.right != self.tail:
                if node.right == t:
                    self.visit(node)
                else:
                    stack.append(node)
                    node = node.right
                    break
            else:
                self.visit(node)
        if len(stack) == 0:
            done = 1

"C로 배우는 알고리즘"을 그대로 작성한 것으로, Python 코드를 작성해서 동일한 결과를 얻을 수는 있었습니다만, 충분히 이해하지는 못하고 있습니다.

3. 실행 코드

실행 코드는 다음과 같습니다.

# main() function
if __name__ == "__main__":
    # Change infix notation to postfix notation
    source = ['A', 'B', '+', 'C', 'D', '-', '*', 'E', '/', 'F', 'G', '*', '+']

    tree = Tree()
    tree.make_parse_tree(source)

    print("[Preorder]")
    print("    Recursive : ", end=' ')
    tree.preorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.preorder_traverse_nr(tree.head.right)
    print()

    print("[Inorder]")
    print("    Recursive : ", end=' ')
    tree.inorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.inorder_traverse_nr(tree.head.right)
    print()

    print("[Postorder]")
    print("    Recursive : ", end=' ')
    tree.postorder_traverse(tree.head.right)
    print()
    print("Non Recursive : ", end=' ')
    tree.postorder_traverse_nr(tree.head.right)
    print()

4. Tips

1. Python에서 리스트의 복사와 관련해서 잘 정리된 문서^[각주:1]를 참고하세요.

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_04/Ch_04_02.py

6. 기타

주로 "C로 배우는 알고리즘"에 적혀 있는 내용을 주고 사용하고, 필요시 인터넷 검색의 결과를 이용하였습니다. 이용한 출처는 밝히는 것을 원칙으로 합니다만, 혹시 실수가 있거나 문제되는 사항이 있다면 알려 주십시오. 수정하도록 하겠습니다.

1. https://blueshw.github.io/2016/01/20/2016-01-20-shallow-copy-deep-copy/ [본문으로]