[자료구조] 재귀(Recursion)

02. 재귀(Recursion)

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

 

재귀 함수의 흐름은 재귀함수가 복사되는 것이라고 이해하면 쉽다.

"Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 됩니다."

 

- 팩토리얼(Factorial)

$n!$을 계산하는 식은 $(n-1)$항에 대한 일반항으로 나타낼 수 있으므로 재귀함수를 활용하여 나타낼 수 있다.

팩토리얼 일반식

#include <stdio.h>

int Factorial(int n){
    if(n==0) 
        return 1;
    else
        return n*Factorial(n-1);
}

int main(void){
    printf("5! = %d \n", Factorial(5));
}

 

02-2. 재귀의 활용

 

- 피보나치 수열(Fibonacci Sequence)

피보나치 수열 또한 첫번째 항과 두번째 항이 주어진다면 $(n-1)$항에 대한 일반항으로 나타낼 수 있으므로 재귀함수를 활용하여 나타낼 수 있다.

#include <stdio.h>

int Fibo(int n){
    if(n==1)
        return 0;
    else if(n==2)
        return 1;
    else
        return Fibo(n-1) + Fibo(n-2);
}

int main(void){
    int i;
    for(i=1; i<15; i++)
        printf("%d ", Fibo(i));
}

$Fibo(n-1) + Fibo(n-2)$항이 호출될 때, +연산자의 왼편에 있는 Fibo의 recursive호출이 완료된 후에 오른쪽에 있는 Fibo함수의 recursive호출이 진행된다.

 

- 이진탐색알고리즘의 재귀적 구현

이진탐색알고리즘 또한 "동일한 패턴을 반복"하므로 재귀적 성격을 띤다고 볼 수 있다. 따라서 이진탐색알고리즘을 재귀적으로 구현하면 다음과 같다.

#include <stdio.h>
#include <math.h>

int BSearchRecur(int ar[], int first, int last, int target){
    int mid = floor((first+last)/2);

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

int main(void){
    int array[] = {1,3,5,7,9};

    int idx = BSearchRecur(array, 0, (sizeof(array)/4)-1, 7);

    if(idx == -1)
        printf("target이 없습니다.");
    else
        printf("target이 %d에 있습니다", idx);

    return 0;
}

 

02-3. 하노이 타워: The Tower of Hanoi

 

하노이타워 문제는 이해하는데 오랜시간이 걸렸다..

재귀문제를 풀 때 재귀함수 호출순서보다 패턴을 찾는것이 더 핵심이라는 것을 알게해주는 문제였다..

하노이 문제는 호출순서를 하나하나 따라가니 너무 복잡하고 헷갈렸다.

재귀를 활용하여 문제를 풀 때는 "동일한 패턴 찾기"에 집중하자..

 

하노이 타워

그래서 하노이 타워의 동일한 패턴(반복패턴)은 무엇인가?

1. 작은 원반 $n-1$개를 A에서 B로 이동

2. 큰 원반 1개를 A에서 C로 이동

3. 작은 원반 $n-1$개를 B에서 C로 이동

 

이 반복패턴을 활용하여 코드를 짜면 다음과 같다.

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to){
    if(num==1){
        printf("원반 1을 %c에서 %c로 이동\n", from, to);  //매번 마지막 원반을 to위치로 옮김
    }
    else{
        HanoiTowerMove(num-1, from, to, by);  //n-1개의 원반을 A에서 B로 옮겨야 가장 큰 원반을 A에서 C로 옮길 수 있다. (1번 반복패턴)
        printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);  //가장 큰 원반을 A에서 C로 옮긴다. (2번 반복패턴)
        HanoiTowerMove(num-1, by, from, to);  //A에서 B로 옮겨졌던 n-1개의 원반을 B에서 C로 옮긴다. (3번 반복패턴)
    }
}

int main(void){
    //막대 A의 원반 3개를 막대 B를 경유하여 막대 C로 옮기기
    HanoiTowerMove(3, 'A', 'B', 'C');

    return 0;
}

하노이 문제는 재귀 공부할 때 종종 보면서 연습하면 좋을것같다....