[자료구조] 240606~240608 학습일기 - ch2. 재귀(Recursion)

윤성우의 열혈 자료구조 - 예스24

---

1. 재귀 함수

1-1. 재귀함수의 흐름

Recursive라는 재귀함수가 있다고 가정.

 

- 함수가 호출되는 구조: 함수가 호출되면, 해당 함수의 복사본이 만들어져서 복사본이 실행된다.

함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행된다.

 

따라서 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조다.

Recursive 함수를 실행하는 중간에 Recursive 함수가 호출되면(재귀함수이기 때문) , Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다.

 

1-2. 재귀함수의 활용

재귀함수는 매우 많은 수의 함수 호출을 동반한다. 따라서 성능상의 불리함은 존재한다.

 

1-3. 피보나치 함수(재귀함수로 구현한 것)의 함수 호출 진행순서

return Fibo(n-1) + Fibo(n-2)

의 구조를 가지는 피보나치 함수 Fibo가 있을 때, + 연산자의 왼편에 있는 Fibo 함수 호출(여기서는 Fibo(n-1))이 완료되어야 비로소 오른편에 있는 Fibo 함수(Fibo(n-2)) 함수 호출이 진행된다.

 

 

2. 재귀함수로 구현한 Binary Search 알고리즘

#include <stdio.h>

int BSearchRecur(int arr[], int first, int last, int target){
  if (first>last) {
    return -1;
  }
  
  int mid = (first+last)/2;
  if (arr[mid]== target){
    return mid;
  } else if (arr[mid]< target){
    return BSearchRecur(arr, mid+1, last, target);
  } else {
    return BSearchRecur(arr, first, mid-1, target);
  }
}

void main(){
  int arr[] = {1,3,5,7,9};
  int result = BSearchRecur(arr, 0,sizeof(arr)/sizeof(int)-1, 1);

  if (result==-1){
    printf("Recursive Binary Search 실패");
  } else {
    printf("Recursive Binary Search 성공");
    printf("\nIndex: %d", result);
  }
}

콘솔 출력

Recursive Binary Search 성공
Index: 0

 

 

3. 재귀함수로 구현한 하노이타워 문제

 

3-1. 하노이 타워

막대 3개(A,B,C)와 원반 n개가 있을 때,

막대 A에 있던 원반 n개를 막대 C로 옮겨야 한다.

 

이때 원반은 한 번에 하나씩만 옮길 수 있다. 그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

 

3-2. 하노이 타워에서 원반 3개를 옮기기

노트에 써서 한번 풀어보았다.

여기서는 원반 하나하나를 A,B,C라 설정했다. 

 

3-3. 하노이 타워 문제의 해결

💡세 개의 원반을 막대 C에 옮기는 문제를 해결하기 위해서는 두 개의 원반을 막대 B에 옮기는 문제부터 해결해야한다.

 

막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 재귀적으로 구성된다.

① 작은 원반 n-1개를(맨 아래의 원반을 제외한 나머지 원반을) A에서 B로 이동 [=> 원반 n-1개에 대한 하노이타워 문제]

② 가장 큰 원반(맨 아래의 원반) 1개를 A에서 C로 이동

③ 작은 원반(위의 1단계에서 옮겨진 원반) n-1개를 B에서 C로 이동 [=> 원반 n-1개에 대한 하노이타워 문제]

 

한 막대기에 정렬되어있는 n-1개의 원반들을 목적지로 옮기기 위해서는 반드시 매개 막대가 필요하다.(코드에서는 by로 표현됨.)

 

#include "stdio.h"

// from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동
void HanoiTowerMove(int num, char from, char by, char to){
  if (num==1){ //탈출 조건
    printf("원반 1을 %c에서 %c로 이동\n", from, to);
  } else{
    HanoiTowerMove(num-1, from, to,by);
    printf("원반 %d을 %c에서 %c로 이동\n", num,from, to);
    HanoiTowerMove(num-1, by, from,to);
  }
}

void main(void) {
  HanoiTowerMove(3, 'A','B','C');
}

콘솔 출력

원반 1을 A에서 C로 이동
원반 2을 A에서 B로 이동
원반 1을 C에서 B로 이동
원반 3을 A에서 C로 이동
원반 1을 B에서 A로 이동
원반 2을 B에서 C로 이동
원반 1을 A에서 C로 이동