[Data Structure] Chapter 02: 재귀(Recursion)

재귀함수를 이해하고, 이를 활용하여 팩토리얼·피보나치 수열 등 여러 함수를 구현해보자.

 

 

재귀함수의 기본적인 이해

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

출처: https://imhere0729.tistory.com/3

 재귀함수의 작동 원리는 위 그림의 형태와 같이 별도로 설정하지 않으면 멈추지 않고 계속 실행된다. 따라서, 특정 조건을 충족했을 때 재귀함수 호출이 멈추도록해야 하는데, 여기서 이 조건을 '재귀의 탈출조건'이라 한다. 

 

 이와 관련된 예제를 살펴보자.

#include <stdio.h>

void Recursive(int num)
{
    if(num <= 0)    //재귀의 탈출조건
        return;     //재귀의 탈출
    printf("Recursive call! %d \n", num);
    Recursive(num-1);
}

int main(void)
{
    Recursive(3);
    return 0;
}

Recursive call! 3 
Recursive call! 2 
Recursive call! 1

-> Recursive 함수에 0이 전달되면 '재귀의 탈출조건' 성립

 

팩토리얼: factorial

• 팩토리얼의 수식적 의미는 다음과 같다. $n! = n * (n-1) * (n-2) *  . . . .  * 2 * 1$
• 이를 다시 표현하면 다음과 같아진다. $n! = n * (n-1)!$
• n=0일 때, 팩토리얼의 값은 1이다.

#include <stdio.h>

int Factorial(int n)
{
    if(n == 0)	//n이 0일 때
        return 1;
    else 	//n이 1 이상일 때
        return n * Factorial(n-1);
}

int main(void)
{
    printf("1! = %d \n", Factorial(1));
    printf("2! = %d \n", Factorial(2));
    printf("3! = %d \n", Factorial(3));
    printf("4! = %d \n", Factorial(4));
    printf("9! = %d \n", Factorial(9));

    return 0;
}

1! = 1 
2! = 2
3! = 6
4! = 24
9! = 362880

 

피보나치 수열: Fibonacci Sequence

• $수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값$
• n=1일 때, 피보나치 수열의 값은 0이다.
• n=2일 때, 피보나치 수열의 값은 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));

    return 0;
}

0 1 1 2 3 5 8 13 21 34 55 89 144 233

 

 코드의 실행흐름을 나타내자면 다음과 같아진다.

#include <stdio.h>

int Fibo(int n)
{
    printf("func call param %d \n", n);
    
    if(n == 1)
        return 0;
    else if(n == 2)
        return 1;
    else 
        return Fibo(n-1) + Fibo(n-2);
}

int main(void)
{
    Fibo(7);
    return 0;

    return 0;
}

func call param 7 
func call param 6
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1

 

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

• Chapter 01에서 구현한 이진 탐색 알고리즘은 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다.

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)
{
    int mid;
    if(first>last)
        return -1;

    mid = (first+last) /2;

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

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

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx == -1)
        printf("탐색 실패 \n");
    else
        printf("타겟 저장 인덱스: %d \n", idx);

    return 0;
}

 

하노이 타워: The Tower of Hanoi

하노이 타워 문제

• 모든 원반을 같은 형태로 A에서 C로 옮겨야 한다.
• 원반은 한 번에 하나씩만 옮길 수 있고, 옮기는 과정에서 작은 원반의 위에 큰 원반이 올라오면 안 된다.
• 위에서부터 순서대로 원판1, 원판2, 원판3 ...

 

하노이 타워의 반복패턴

1. 가장 아래에 있는 원반을 제외한 나머지 모든 원판을 B로 옮긴다.
2. 가장 아래에 있는 원반을 C로 옮긴다.
3. 나머지 원반을 모두 C로 옮긴다.

이를 일반화시킨 과정을 다음과 같다.

 

1. 작은 원반 n-1개를 A에서 B로 이동
2. 큰 원반 1개를 A에서 C로 이동
3. 작은 원반 n-1개를 B에서 C로 이동
4. 이동해야 할 원반의 개수가 1개인 경우 그냥 A에서 C로 옮긴다.

 

하노이 타워 문제의 해결

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)   //num개의 원반을 from에서 by를 이용해서 to로 이동
{
    if(num==1)
    {
        printf("원반1을 %c에서 %c로 이동 \n", from, to);    //반복 패턴의 4단계
    }
    else
    {
        HanoiTowerMove(num-1, from, to, by);    //반복 패턴의 1단계
        printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);  //반복 패턴의 2단계
        HanoiTowerMove(num-1, by, from, to);    //반복 패턴의 3단계
    }
}

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

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

-> 함수 호출 순서, 코드의 실행흐름을 파악하려 애쓰지 말고 직관적으로 이해하자.

---

참고자료

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11
• https://imhere0729.tistory.com/3

[자료구조]재귀함수