[자료구조] 번외1. 재귀(Recursion)

재귀(Recursion)

재귀는 어떠한 자료구조나 ADT는 아니나 자료구조를 다룰 때 자주 나오는 개념이기에 소개한다.

재귀란 자기 스스로를 호출하여 반복하는 것이다. 재귀의 반대되는 개념으로는 iterative가 있다. 재귀함수와 for문의 관계라고 생각하면 된다.

# 재귀 함수의 예시
def say_hello():
    print("Hello!")
    say_hello()

 

이런 재귀 알고리즘을 사용하는 이유는 우선 '사람'이 보고 이해하기 좋기 때문이다. iterative 하게 구현하는 것이 계속해서 재귀함수가 스택 메모리에 쌓이는 것을 방지하기에 성능면에서는 더 뛰어날 것이다. 특히 이진 탐색이나 위상 정렬등에서 재귀적으로 사고하는 것이 이해하기에 편하다.

구현

따로 재귀 함수에 구현이라 할 것은 없지만, 구현시에 주의할 점을 소개한다.

반복되는 재귀 함수에는 이러한 재귀를 멈출 base cases가 존재해야 한다. 그렇지 않다면 재귀함수는 영원히 반복하게 될 것이다. 다음 예시를 보자.

def add(n: int):
    if n == 1:
        return 1
    return add(n-1) + 1

위의 코드에서 n == 1인 경우가 base case라 할 수 있다.

Linear recursion

Linear recursion은 자기 자신을 한 번만 호출하는 재귀 함수라 볼 수 있다. 즉 base case 검증 -> 자기 자신 재귀 호출의 과정으로 돌아간다고 볼 수 있다. 이러한 재귀들은 대체로 간단하게 iterative 한 방식으로도 구현할 수 있다.

Tail recursion

재귀 함수의 단점은 계속해서 함수가 스택에 쌓여가며 비효율이 발생한다는 것이다. 이런 단점을 극복하기 위해 꼬리 재귀(tail recursion)라는 방식이 존재한다.

꼬리 재귀의 사용을 하려면, 추가연산이 필요 없게 재귀 함수 마지막 재귀 호출 시에 자기 스스로를 return 해주게 작성하면 된다. 이런 방식으로 코드를 작성하면 쉽게 iterative 한 방식으로 변경이 가능하기에 컴파일러단에서 최적화를 해준다.

Binary recursion

base case가 아닌 경우에 2개의 재귀 함수를 호출하는 것을 binary recursion이라 한다. 이진트리 노드의 합을 구하는 경우 등에 사용할 수 있다.