[알고리즘] 재귀 알고리즘

안녕하세요, 오랜만에 알고리즘 포스팅으로 돌아왔습니다! 이제 공채시즌인 만큼 코딩테스트를 준비하다보니 이렇게 알고리즘 글을 올리게 되었어요ㅎㅎ 우리 모두 공부 열심히 해서 원하는 기업합격해요:)

 

재귀 알고리즘

재귀 알고리즘이란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것을 말합니다. 실생활에서의 문제를 해결하기 위해 재귀 알고리즘이 많이 사용됩니다. 

 

간단한 구현을 통해 재귀 알고리즘에 대해 알아보겠습니다. 피보나치 순열에 대해 아시나요?

피보나치 순열이란, F₀ = 0, F₁ = 1, F₂ = F₀+F₁, ... ,F_n = F_n-2+F_n-1  형태로 흘러가는 순열을 말합니다. 이 순열을 간단하게 재귀함수로 구현해보겠습니다.

def fb_re(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    elif x>=2:
        return fb_re(x-2) + fb_re(x-1)

이번엔, 피보나치 순열을 반복문을 사용하여 구해보겠습니다.

def fb_it(x):
    answer = 0
    a = 0
    b = 1
    while x > 0:
        x -= 1
        a, b = b, a+b
        answer = fa
    return answer

이렇게, 반복문으로 구현하기 복잡한 문제를 재귀 알고리즘을 사용하여 훨씬 간단하게 해결할 수 있습니다.

 

그렇다면, 모든 케이스에서 반복문보다 재귀 알고리즘이 좋을까요?

우선, 시간복잡도를 따져봅시다.

재귀 알고리즘은 구하고자 하는 값이 커질수록 재귀를 여러 번 하기 때문에 O(n)의 시간복잡도를 갖는다고 볼 수 있습니다.

반복문또한 구하고자 하는 값이 커질수록 여러 번 반복하기 때문에 O(n)의 시간복잡도를 갖는다고 볼 수 있습니다.

 

재귀알고리즘은 반복문과 비슷하게 종결조건이 매우 중요합니다. 알고리즘의 경우, 유한한 시간 내에 답이 나와야 하기 때문에 종결조건을 만드는 것에 큰 주의를 기울여야 합니다.

 

이렇게 재귀 알고리즘에 대해 알아보았습니다.

정리하자면, 재귀 알고리즘은 사람의 생각을 소스코드로 구현하기 좋은 알고리즘입니다. 그러나, 반복문에 비해 효율성이 떨어지기 때문에 성능 상에서 문제를 일으킬 수 있으니 주의하셔야 합니다.