알고리즘: Recursion

Recursion?

재귀는 특정 함수 내에서 함수 자신을 다시 호출하는 것을 의미한다. 재귀는 Stack의 특성을 그대로 반영하여, 가장 최근에 호출된 함수 부터 처리되는 방식으로 진행된다. 재귀를 잘 다룰 수 있다면 DFS와 백트래킹, 트리 탐색과 같은 문제를 해결 할때 효율적으로 접근할 수 있게 된다.

 

---

이진 트리 순회

Figure 1. Depth 3의 이진 트리

그림 1과 같은 이진 트리가 있을 경우, 3가지 방식으로 트리를 순회할 수 있다. 첫 번째는 전위 순회로 1-2-4-5-3-6-7 순서로 트리를 순회한다. 두 번째는 중위 순회로 4-2-5-1-6-3-7 순서로 트리를 순회 한다. 마지막으로 후위순회는 4-5-2-6-7-3-1로 순회한다. 트리를 순회하는 것은 재귀 호출을 통해서 구현 할 수 있다.

 

 

Simple Tree Travel

def tree_travel(num, order):
    if num > 7:
        return
    else:
        if order == 'pre':
            print(num, end=' ')
            tree_travel(num * 2, order)
            tree_travel((num * 2) + 1, order)
        elif order == 'in':
            tree_travel(num * 2, order)
            print(num, end=' ')
            tree_travel((num * 2) + 1, order)
        else:
            tree_travel(num * 2, order)
            tree_travel((num * 2) + 1, order)
            print(num, end=' ')


tree_travel(1, 'pre')
print()
tree_travel(1, 'in')
print()
tree_travel(1, 'post')

• 전위 순회(pre)인 경우, 접근한 노드 - left child - right child 순으로 처리한다.
• 중위 순회(in)의 경우, left child - 접근한 노드 - right child 순으로 처리한다.
• 후위 순회(post)의 경우 left child - right child - 접근한 노드 순으로 처리한다.
• 실행 결과는 위의 설명과 동일한 방식으로 호출된다.