2. 재귀

1. 함수의 재귀적 호출 이해

• 완료되지 않은 함수를 호출한다???
  => 함수의 복사본이 만들어져서 실행된다고 생각하면 편함
  
  

2. 재귀의 활용

• 잘 정의하는것이 중요함
• 재귀함수의 호출 순서가 중요한게 아니라 함수 자체를 이해해야 함
• 저번에 했던 이진 탐색을 재귀로 구현해보기(동일한 패턴을 반복하기 때문에 가능)
  1. 중앙에 목표 값이 있는지 확인
  2. 아니라면 탐색 범위를 반으로 줄여서 다시 탐색

  int BSearch(int ar[], int frist, int last, int target){
  	//탈출조건
    if(first > last)
    	return -1;
    
    int mid = (first + last)/2;
    if(ar[mid] == target)
    	return mid;
    
    if(ar[mid] < target)
    	BSearch(ar, first, mid-1, target);
    else
    	BSearch(ar, mid+1, last, target);
  }

3. 하노이 타워

• 원반은 한번에 하나씩만 옮길 수 있고 작은 원반 위에 큰 원반이 올라갈 수 없음

• A에 있는 n개의 워반을 C로 옮긴다고 할 때

  1. n-1개의 원반을 A -> B 로 이동
  2. 남아있는 1개의 원반을 C로 이동
  3. B에 있는 n-1개의 원반을 B -> C로 이동

//n개를 from에서 by를 경유해 to로 이동
void HanoiMove(int num, char from, char by, char to){
	
    if(num == 1)
    	pritntf("원반1을 %c에서 %c로 이동 \n", from, to);
    else{
		HanoiMove(num-1, from, to, by); //n-1개를 from에서부터 to를 거쳐 by로 이동
        printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
		HanoiMove(num-1, by, from, to); //n-1개를 by에서부터 from을 거쳐 to로 이동
    }
}

void main(){

	//막대 A에 있는 원반을 B를 경유해 C로 이동
    HanoiMove(3, 'A', 'B', 'C');
}