Algorithm_#3 재귀(recursion)

재귀(Recursion)

-> 함수 내부에서 한번 이상 자신의 함수를 호출

-> 알고리즘 내부에서 한번 이상 자신의 알고리즘을 호출

예 1) 1+2+…+n

sum(n) = 1+2+...+(n-1)+n

sum(n-1)
```
def sum(n):
	if n == 1: return 1
    return sum(n-1) + n
```
- 수행시간:
  
  => T(n) = cn = O(n)

재귀함수

n==1 테스트: 바닥조건 base case: T(n)=1 or c

재귀 호출: T(n) = 점화식

위 두 정보를 이용하여 점화식

예 2: sum(a,b) = a+(a+1)+ … + (b-1) (가정: a <= b)

=> 반 나눠서 생각!

sum(3,8) = 3+4+5 + 6+7+8

sum(3 , 5) sum(6,8)
```
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) = T(n/2) + T(n/2) + c
  
  = 2T(n/2) + c
  
  (n = 2^k이라 가정)
  
  = 2cn - c
  
  = O(n)
- 점화식:

수행시간

T(n) = T(n-1) + c (예제 1과 동일)

= O(n)

예 3: reverse 함수

-> 거꾸로
1. reverse(A) = reverse ( ) + A[0]
= reverse(A[1:]) + A[:1]

리스트

`=> 맨 처음 것을 계속 뒤로 붙이기
- 수행시간
  
  T(n) = T(n-1) + c (예제 1과 동일)
  
  = O(n)
1. reverse(A,start, stop) = A[start] … A[stop-1]
  
  = A[stop-1] reverse(A[start + 1]... A[stop-2]) A[start]
  
  = A[stop-1] reverseA[start + 1]... A[stop-2] A[start]
  
  => 맨 처음과 맨 뒤를 바꾸기
- 수행시간
  
  T(n) = T(n-2) + c
  
  = T(n-4) + c + c
  
  …=T(1) + n/2 * c
  
  = O(n)