재귀 알고리즘(recursive algorithms)

재귀 알고리즘은 이름이 재귀인 알고리즘이 아니라, 재귀의 특성을 지닌 알고리즘이라는 뜻이다.

주어진 문제에 대하여 재귀를 사용한다면 보다 코드를 간결하게 작성하여 문제를 해결할 수 있다.

ex 1) sum(n) = n + sum(n-1) : sum(n) 을 구하기 위해 sum(n-1)이라는 sum 함수를 또 불러옴.

ex 2) 이진 트리(binary tree), 순열(Factorial), 자연수의 합 등등

하지만 재귀 알고리즘을 사용할 때는 항상 종결 조건(trivial case)을 명시해야 한다.

-> 재귀 알고리즘이 사용되는 반복문에서 무한한 반복이 일어날 수 있기 때문

ex 1) sum(n) = n + sum(n-1) 에서 n이 음수까지 진행될 수 있음.

ex 2) 피보나치 순열 구현 예제

def solution(x):
#    Recursion # 재귀
     if x == 0:  # 종결 조건
         return 0
     elif x == 1:
         return 1
     else :
         return solution(x-1) + solution(x-2)

#    Iteration # 반복
    list = []
    for i in range(0,x+1): # i가 0부터 x까지 반복
        if i<2:  # 종결 조건
            list.append(i)
        else :
            list.append(list[i-1]+list[i-2])
    return list[x]
        
    
    # 1 1 2 3 5 8 13 21 39 ...

• 재귀 알고리즘은 동일한 함수가 중복되어 실행될 가능성이 있으므로 다소 효율성이 떨어질 수 있다.

fib(2)나 fib(1),fib(0) 등이 여러번 실행됨을 알 수 있다. (불필요한 중복 호출 多)

# 재귀 이진 탐색
def solution(L, x, l, u):
    if u<l : # trivial case
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L,x,l,mid-1)
    else:
        return solution(L,x,mid+1,u)

위 trivial case의 경우 타겟 원소가 리스트에 없을 경우 -1이 return 되는 경우이다.

이는 타겟 원소가 없을 경우(l=mid=u)에 이진 탐색이 재귀적으로 수행될 때, l = mid+1이 되면서 l > u 가 되어 버린다.

 

사진 출처 : http://www.xn--299as6vb5i1je.com/interview/12