재귀 함수 / 재귀 함수

 

재귀 함수 / 재귀 함수

 

 

재귀 함수 (Recursive Function)

 

자기 자신을 호출하는 함수

 

def countdown(n):
    if n > 0:
        print(n)
        countdown(n - 1)

countdown(4)

#<Run>
#4
#3
#2
#1

---

재귀 활용 예시

 

재귀적으로 문제를 푼다는 것 = 같은 형태의 더 작은 문제를 푸는 것 = 부분 문제의 답을 이용해서 기존 문제를 푸는 것

 

팩토리얼(!) 예제

 

5! = 1 x 2 x 3 x 4 x 5 = 120

4! = 1 x 2 x 3 x 4 = 24

0! = 1

 

n! 에서 n = 0 인 경우, n! = 1  (base case)

n! 에서 n > 0 인 경우, n! = (n-1)! x n  (recursive case)

def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1) * n

print(factorial(4))

#<Run>
#24

 

Base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우

Recursive case : 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우

---

 

재귀 함수 vs 반복문

 

재귀 함수로 작성 가능한 코드는 반복문으로도 작성 가능.

반복문으로 작성 가능한 코드는 재귀 함수로도 작성 가능.

 

하지만, 함수를 호출할 때마다 함수를 실행하고 다시 호출한 위치로 돌아갈 때 그 위치를 저장해놓는 것을 Call Stack 이라고 하는데, 함수의 호출이 너무 많아지면 Call Stack 이 쌓이게 되어 StackOverflow 에러가 뜨게 된다.

 

즉, 함수 호출이 많아져서 StackOverflow 의 위험성이 생긴다면 재귀 함수를 쓰면 안되지만 재귀 함수가 더 깔끔하거나 효율적일 때도 있고, 반대로 반복문을 쓰는 게 더 깔끔하거나 효율적일 때가 있다.

---

def fib(n):
    if n < 3:
        return 1
    
    return fib(n - 1) + fib(n - 2)

for i in range(1, 11):
    print(fib(i))

#<Run>
#1
#1
#2
#3
#5
#8
#13
#21
#34
#55

재귀 함수 예제 - 피보나치 수열

 

피보나치 수열 : 첫 번째 항과 두 번째 항이 1이고, 세 번째 항부터는 바로 앞의 두 항의 합으로 정의된 수열

---

def triangle_number(n):
    # base case
    if n == 1:
        return 1
    # recursive case
    return n + triangle_number(n - 1)

for i in range(1, 11):
    print(triangle_number(i))

#<Run>
#1
#3
#6
#10
#15
#21
#28
#36
#45
#55

재귀 함수 예제 - 숫자 합

 

시간 복잡도 : triangle_number 함수는 총 n번 호출되니까, 총 O(n) 의 시간이 걸린다.

---

def sum_digits(n):
    # base case
    if n < 10:
        return n

    # recursive case
    return n % 10 + sum_digits(n // 10)

print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

#<Run>
#14
#15
#16
#11
#20

재귀 함수 예제 - 자릿수 합

 

시간 복잡도 : 인풋 n 의 자릿수 개수를 d 로 표현한다면, sum_digits 의 시간 복잡도는 O(d) 이다. 재귀적으로 sum_digits 가 호출될 때마다 n은 약 1/10으로 줄어들기 때문에 매번 한 자리씩 줄어든다고 볼 수 있다.

---

def flip(some_list):
    # base case
    if len(some_list) == 0 or len(some_list) == 1:
        return some_list

    # recursive case
    return some_list[-1:] + flip(some_list[:-1])

some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

#<Run>
#[9, 8, 7, 6, 5, 4, 3, 2, 1]

재귀 함수 예제 - 리스트 뒤집기

 

알고리즘 : some_list 의 길이가 0 이나 1인 경우에 답을 바로 생각해낼 수 있다(base case). 그게 아니라면 배열 원소중에서 가장 뒤에 있는 원소를 가장 앞으로 배치한 후 해당 원소를 제외한 나머지 모든 원소들의 리스트를 뒤집는다.

 

some_list[-1:] : 가장 오른쪽 값

some_list[:-1] : 가장 오른쪽 값을 제외한 모든 원소

 

시간 복잡도 : some_list 의 길이를 n 이라고 하자. some_list[-1:] 은 시간 복잡도가 O(1) 이고, some_list[:-1] 은 시간 복잡도가 O(n-1) 이다. 재귀적 부분을 제외한 flip 함수의 시간 복잡도는 O(n) 인 것이다. 그리고 매 호출마다 리스트의 길이가 1 씩 줄기 때문에, flip 함수는 총 n번 실행된다. 그래서 총 시간 복잡도는 O(n제곱)이다.

---

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # start_index가 end_index보다 크면 some_list안에 element는 없다
    if start_index > end_index:
        return None
      
    # 범위의 중간 인덱스를 찾는다
    mid = (start_index + end_index) // 2
  
    # 이 인덱스의 값이 찾는 값인지 확인을 해준다
    if some_list[mid] == element:
        return mid

    # 찾는 항목이 중간 값보다 작으면 리스트 왼쪽을 탐색해준다
    if element < some_list[mid]:
        return binary_search(element, some_list, start_index, mid - 1)

    # 찾는 항목이 중간 값보다 크면 리스트 오른쪽을 탐색해준다
    else:
        return binary_search(element, some_list, mid + 1, end_index)        

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

#<Run>
#0
#None
#2
#1
#4

재귀 함수 예제 - 이진 탐색 재귀로 구현해보기

 

base case : 리스트에 해당 원소가 없을 때, 해당 인덱스의 값(중간값)이 해당 원소와 같을 때

 

base case 가 아니라면 중간값과 해당 원소값의 대소를 비교하며 범위를 줄여나간다. (이진 탐색 알고리즘)

 

리스트에 해당 원소가 없을 때 = 처음 인덱스가 마지막 인덱스보다 클 때 -> 처음 인덱스와 마지막 인덱스의 값이 같으면, 탐색 범위의 크기는 1인데 이 때도 해당 원소를 찾지 못한다면 리스트에 해당 원소가 존재하지 않는 것.

 

시간 복잡도 : 탐색 범위가 반 씩 줄어들기 때문에, 시간 복잡도는 O(lg(n)) 이다.