자료구조 - 1. 재귀

자료구조란?

데이터의 표현 및 저장방법

 

재귀함수란

재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

 

함수가 아직 끝나지 않았는데 다시 호출할 수 있는가? 할 수 있다.

재귀함수의 흐름을 이해하기 힘들다면 함수의 원본이 따로 있고 해당 재귀함수에서 재귀함수가 호출될 때마다 함수의 복사본이 만들어져서 그 복사본이 실행된다고 생각하면 이해하기 쉽다.

 

재귀함수의 예 : n 팩토리얼

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

Factorial(4);을 실행하면 Factorial(4) 함수 내부에서 Factorial(3)을 호출하고 다시 그 안에서 Factorial(2)를 호출하고 다시 Factorial(1)을 호출함으로써 재귀적인 함수 호툴이 일어나고 마지막에 1이 리턴 된다.

 

이를 수식으로 나타내면 다음과 같다.

Factorial(n) = n * Factorial(n-1)  ......(n≥1)
Factorial(n) = 1                   ......(n=0)

 

---

재귀함수의 활용

1. 피보나치 수열

피보나치 수열이란, 다음과 같은 형태를 띠는 수열로,

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ......................................

앞의 원소 두 개를 더해서 현재의 수를 만들어가는 수열이다.

즉, 수식으로 표현하면 다음과 같다.

fibo(n) = 0                       ... n = 1
        = 1                       ... n = 2
        = fibo(n-1) + fibo(n-2)   ....그 외

이 수학적 재귀의 표현을 그대로 코드로 옮기면 다음과 같다.

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

다만, 재귀함수는 매우 많은 수 의 함수 호출을 동반하기 때문에 성능상 불리하다. n이 클수록 같은 인자를 가지는 함수가 여러번 호출된다. 따라서 다음과 같이 배열을 이용해 값을 미리 저장해두고 꺼내쓰는 방식으로 구현하는게 더 빠르다.

int Fibo(int n)
{
    // n은 1이상.
    int arr[100];
    arr[1] = 0;
    arr[2] = 1;

    if(n > 2) {
        for(int i=3; i<=n; i++)
            arr[n] = arr[n-1] + arr[n-2];
    }
    
    return arr[n];
}

 

2. 하노이 타워 문제

하노이 타워 문제는 [하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법]에 관한 문제다.

제약조건은 다음과 같다.

① 원반은 한 번에 하나씩만 옮길 수 있다.

② 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안 된다.

 

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

 

그렇다면 원반이 4개, 7개, 10개로 늘어나면 어떻게 옮길까?

이를 재귀 호출을 이용해 해결할 수 있다. 원반이 4개라면 원반 3개를 막대 B로 옮긴 다음 제일 큰 4번 원반을  막대 C로 올기고 다시 원반 3개를 C로 옮기면 된다. 즉, N개의 원반 문제를 풀려면 N-1개의 원반 문제를 풀면 된다.

 

알고리즘은 다음과 같다.

1. 원반이 1개 일때, 그냥 옮긴다. (종료조건)
2. 원반이 n개 일때,
    1) 작은 원반 n-1개를 A에서 B로 이동
    2) 큰 원반 한 개를 A에서 C로 이동
    3) 작은 원반 n-1개를 B에서 C로 이동

코드로 나타내면 다음과 같다.

void HanoiTowerMove(int num, char from, char by, char to)
{
    // num은 원반 개수, from은 현재 위치, by는 거쳐갈 위치, to는 도달해야 할 목적지
    if(num == 1)
        printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);
    else {
        // 1) 작은 원반 n-1개를 A에서 B로 이동
        HanoiTowerMove(num-1, from, to, by);
        // 2) 큰 원반 한 개를 A에서 C로 이동
        printf("원반 %d를 %c에서 %c로 이동\n", num, from, to);
        // 3) 작은 원반 n-1개를 B에서 C로 이동
        HanoiTowerMove(num-1, by, from, to);
    }
}