[자료구조] Chapter 02. 순환(Recursion, 재귀)

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

-함수 호출 or 되돌아 갈 때 주소의 큰 이동 : jump
-돌아올 때 : 가장 마지막으로 호출한 곳으로 돌아감 (호출의 역순)

순환

: 함수를 정의할 때 자신을 인용하는 형태로서, 큰 size의 문제를 작은 size의 문제들로 분해하여 해결하는 방식

✓ C2의 유무에 따라 꼬리재귀인지 아닌지로 나뉨(있으면 꼬리재귀 X, 없으면 꼬리재귀 O)
✓ 모든 순환함수는 비순환 함수로 바꿀 수 있음

• 순환함수 장단점
  • 장점 : 알고리즘 설계 및 구현 쉽다.
  • 단점 : 느릴 수 있다 (<- 중복연산 있음)
  ex) 피보나치 수열
  
  ex) Divide & Conquer (분할 정복법)
  1. 분할(devide) : 동일한 유형의 작은 크기
  2. 정복(conquer) : 각각 해결 (순환 호출)
  3. 병합(combine) : 작은 결과들을 종합
  

Merge Sort

Ms(int l, int h) {
	if(l >= h) return // 재귀호출에는 조건 test 필수!! , data 개수 1개 이하는 sorting 필요 X
    m = (l + h)/2
    Ms(l, m)
    Ms(m+1, h)
    Merge(l, m, h) // 병합
}

• 분석
  

Hanoi Tower Puzzle : 하노이탑 문제

1. 한 번에 1개의 디스크만
2. 언제나 큰 것이 아래쪽
3. 최소의 움직임

HT(n, S, D, T) {
	if(n = 0) return
    HT(n-1, S, T, D)
    S -> D
    HT(n-1, T, D, S)
}

• 분석