[신찬수 교수님] 3. 재귀(Recursion)

재귀(Recursion)

재귀함수 = 함수 내부에서 한번 이상 자신의 함수를 호출하는 것
재귀알고리즘 = 알고리즘 내부에서 한번 이상 자신의 알고리즘을 다시 적용해서 문제를 푸는 것

 

예1

#1부터 n까지 더하는 재귀함수

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

위 재귀함수의 시간복잡도는 T(n) = O(n)이 된다.

1. n == 1 테스트 : 바닥조건 (base case) -> T(1) = 1 or C

2. 재귀호출 -> T(n) = 점화식

 

예2

# a부터 b까지 더하는 재귀함수

def sum(a, b):
  if a == b :
    return a
  if a > b :
    return 0
  m = (a + b) // 2
  return sum(a, m) + sum(m + 1, b)

위 재귀함수의 시간복잡도는 T(n) = O(n)이 된다.

 

예3

A =[1, 2, 3, 4, 5]를 A =[5, 4, 3, 2, 1]로 뒤집는 함수

방법 1

reverse(A)는 reverse(A[1:]) + A[:1]과 같다.

이 재귀함수의 시간복잡도는 T(n) = T(n-1) + C = O(n)이 된다.

 

방법 2

reverse(A, start, stop) = A[start] , ... , A[stop - 1]에서 가운데를 중심으로 대칭되는 위치의 원소를 바꾸면된다.

맨 앞과 뒤의 요소를 바꾸면 이렇게 되고 A[stop - 1] , ... , A[start] 가운데까지 가면서 요소를 하나씩 바꾼다.

그럼 다음 동작인 A[stop - 1] , reverse(A[start + 1] , ... , A[stop - 2]) , A[start]의

reverse(A[start + 1] , ... , A[stop - 1]) = reverse(A, start+1, stop - 2) 라고 볼 수 있다.

이 재귀함수의 시간복잡도는 T(n) = O(n)이 된다.

 

---

오늘 배운 점👀

1. 재귀함수는 시간 복잡도가 O(n)이구나!

2. 배열을 반으로 나눠서 무언가를 해야할 때, 인덱스 1-end와, 2-start를 각각 길이 // 2와 (길이 // 2) + 1를 하면 되겠구나! 파이썬 몫 연산자를 이럴 때 쓰면 되겠다!