[코딩테스트][Python3] 재귀 알고리즘 (Recursive Algorithms) 기초&응용 - 피보나치 순열 함수 만들기

 

1. 재귀 알고리즘 Recursive Algorithms 기초

 

 

 [ 문제 ]

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

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

재귀함수 작성 연습을 의도한 것이므로, 재귀적 방법으로도 프로그래밍해 보고, 반복적 방법으로도 프로그래밍해 보시기 바랍니다.

 

 [ 해답 예시 ]

def fibonacci(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1
    else:
        return fibonacci(x-1) + fibonacci(x-2)

 

 

 

 

2. 재귀 알고리즘 Recursive Algorithms 응용

 

 

 [ 문제 ]

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어지고, 또한 탐색의 대상이 되는 리스트 내에서의 범위 인덱스가 l 부터 u 까지로 (인자로) 정해질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.

인덱스 범위를 나타내는 l 과 u 가 인자로 주어지는 이유는, 이 함수를 재귀적인 방법으로 구현하기 위함입니다. 빈 칸에 알맞은 내용을 채워서 재귀 함수인 solution() 을 완성하세요.

예를 들어,
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 binary_search_2(L, x, l, u):
    if l > u:
        return -1
    mid = (l+u)//2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return binary_search_2(L, x, l, mid-1)
    else:
        return binary_search_2(L, x, mid+1, u)

L1 = [2,3,5,6,9,11,15]
x1 = 6
l1 = 0
u1 = 6
print(binary_search_2(L1, x1, l1, u1))

L2 = [2,5,7,9,11]
x2 = 4
l2 = 0
u2 = 4
print(binary_search_2(L2, x2, l2, u2))