파이썬) 재귀 알고리즘

재귀함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 함수이다.

 

ex) 1부터 n까지의 자연수들의 합을 구하는 함수를 재귀함수를 이용해 풀면 다음과 같이 풀 수 있다.

def sum(n):
  print(n)
  if n <=1:
    return n
  return n+sum(n-1)

sum함수는 return하는 값을 n+sum(n-1) 즉, sum함수를 다시 호출하는 재귀함수이다. 이 때 n<=1인 경우의 조건이 붙는데 이 조건문이 없다면 n은 음수로 무한히 실행되기 때문이다. 이러한 조건문을 종결 조건(trivial case)이라 한다. 문제를 재귀적으로 해결하기 위해서는 종결 조건이 필요하다.

sum(5)

5
4
3
2
1
15

함수를 실행시켜보면 위와 같은 결과가 나온다.

 

많은 경우, 재귀적으로 표현된 알고리즘은 사람이 이해하기는 좋지만 성능이 좋지 않은 경우가 많다.

 

 

* 재귀함수를 이용한 피보나치 수열 

 

문제설명

 

인자로 0 또는 양의 정수인 x 가 주어질 때, Fibonacci 순열의 해당 값을 구하여 반환하는 함수 solution() 을 완성하세요.

Fibonacci 순열은 아래와 같이 정의됩니다.
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2, n >= 2

 

정답

def solution(x):
    if x <= 1:
        return x
    else:
        return solution(x-2) + solution(x-1)

피보나치 수열은 x=0,1인 경우 0,1 고정이기 때문에 x<=1 인경우 x를 return하도록 종결 조건을 주었다. 그 후 재귀적으로 표현하기 위해 return solution(x-2) + solution(x-1)을 이용해 코드를 구성하였다.

 

위 문제를 예시로 효울성 측면을 고려해 보았을 때 만약 solution(4)를 실행 시키면

solution(4)=solution(3)+solution(2) 

-> solution(2)+solution(1)+solution(1)+solution(0)

-> solution(1)+solution(0)+solution(1)+solution(1)+solution(0) 총 9번 함수를 호출하게 된다. 따라서 재귀함수는 좋지 않은 성능을 가지고 있음을 알 수 있다. 하지만 자료구조 특성상 무조건 성능이 나쁘다고 할 수 없고, 주어진 문제에 따라 다른 알고리즘에 비해 좋은 성능이 나오는 경우도 있다. 

 

 

* 이진 탐색을 재귀적 방법으로 풀기

 

L = [2, 3, 5, 6, 9, 11, 15]
x = 6
l = 0
u = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴해야 합니다.

 

또 다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
l = 0
u = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

 

이진 탐색은 앞선 포스트에 있으니 참고하면 된다. 

 

정답

def solution(L, x, l, u):
    if l>u :
        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)

앞서 포스팅했던 이진 탐색 코드와 매우 유사하다. 우선 중앙값이 찾고자 하는 값 x와 같다면 중앙값을 리턴하고,

x가 중앙값보다 작다면 이진 탐색에 의해 중앙값 이상 원소는 날라가게 된다. 이를 재귀적인 방법을 이용하기 위해 return solution(L,x,l,mid-1)로 코드를 구성하고, 반대의 경우도 마찬가지로 구성하였다.

종결 조건이 특이한데 필자는 이전 이진 탐색 코드에 썼던 if x not in L: 를 사용하였다. 이 코드를 사용해도 정답이지만 효율성 문제가 발생했다. 

종결 조건 if l>u: 의 의미를 이해하기 어려운데 그 의미를 예시를 통해 설명하자면

 

만약 L=[1,2,3,4]가 있고 x는 6이라 가정하자

시작값은 1, 끝값은 4, 중앙값은 2가 될 것이다. 이때 중앙값 2는 6보다 작으므로 원소 1, 2는 날라가게된다.

[3,4]가 남게 되고 중앙값은 3이 되는데 3은 6보다 작으므로 3은 날라가게 된다. 

그렇다면 [4]만 남게 되는데 이때 함수는 solution(L,6,3,3)이고 중앙값은 4이다. 4 또한 6보다 작으므로 

return solution(L,x,mid+1,u)가 리턴하게 되고 solution(L,6,4,3)이 실행되게 된다. 하지만 이미 탐색할 L은 없어졌으므로 6은 L내에 없다고 판명나게된다. 즉 l > u 인경우 x는 L내에 없으므로 -1을 리턴하게 되는 방식이다.