[자료구조 - C언어] 재귀함수(Recursion) - Factorial, fib, Hanoi

재귀 함수 (Recursion)

 

재귀 함수는 자기 자신을 참조하는 함수입니다. 

Factorial과 Fibonacci, Tower of Hanoi는 반복 루프를 사용하는 것보다 재귀 함수를 사용할 때 코드를 더 간단하게 이해하기 쉽게 작성할 수 있습니다. 

다만 재귀 함수를 사용하면 메모리에 스택이 계속 쌓이게 되어 효율성은 약간 떨어집니다.

또한, 재귀 함수를 사용할 때는 꼭 탈출구(종료 조건)를 넣어 줘야 합니다. 

 

재귀 함수의 예시 

 

팩토리얼(Factorial)

재귀 함수의 가장 간단한 예시는 팩토리얼이라고 할 수 있습니다.

• loop문 사용 (fact)

-> ret *= i을 사용하여 팩토리얼 구하기

• 재귀 함수 사용 (fact_re)

-> n * fact_re(n - 1)을 리턴하여 팩토리얼 구하기 

 

#include <stdio.h>

//재귀함수 사용
int fact_re(int n) {
    if (n == 0 || n == 1)
        return 1;

    return n * fact_re(n - 1);
}

//루프 사용 (재귀x)
int fact(int n) {

    int ret = 1;

    for (int i = n; i > 0; i--) {
        ret = ret * i;
    }

    return ret;
}

//메인함수
int main(int argc, char* argv[]) {

    printf("loop사용\n");
    for (int n = 1; n < 10; n++) {
        printf("n = %d, fact = %d\n", n, fact(n));
    }

    printf("=================================\n");

    printf("재귀함수 사용\n");
    for (int m = 1; m < 10; m++) {
        printf("m = %d, recursion = %d\n", m, fact_re(m));
    }
    return 0;
}

 

<콘솔 창>

팩토리얼

 

 

피보나치(Fibonacci)

-> 다음 수는 앞의 두 수의 합이 되는 수열 ( 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 )

 

• loop문 (fib_loop)

-> 반복문을 사용하여 값을 한 칸씩 밀어 넣어 피보나치수열을 완성함

• 재귀 함수 (fib_r)

-> fib_r(n - 1) + fib_r(n - 2) (앞의 두 수의 합)을 다음 값으로 출력

 

#include <stdio.h>

//재귀함수
int fib_r(int n) {

    if (n == 0)
        return 0;

    if (n == 1 || n == 2)
        return 1;

    return fib_r(n - 1) + fib_r(n - 2);
}

//루프 사용(재귀 x)
int fib_loop(int n) {
    int t, a = 0;
    int b = 1;

    for (int i = 0; i < n; i++) {

        t = a + b;
        a = b;
        b = t;

    }

    return a;
}

//메인함수
int main(int argc, char* argv[]) {

    printf("loop사용\n");
    for (int i = 1; i <= 10; i++) {
        printf("i = %d, fib = %d\n", i, fib_loop(i));
    }

    printf("==============================\n");

    printf("재귀함수 사용\n");
    for (int i = 1; i <= 10; i++) {
        printf("i = %d, fib = %d\n", i, fib_r(i));
    }

    return 0;
}

 

<콘솔 창>

피보나치

 

 

하노이 타워(Tower of Hanoi)

-> 기둥 1, 2, 3번과 disk 1, 2, 3(오름차순으로 disk크기가 커짐)이 있다고 가정하여

작은 disk가 큰 disk 밑에 들어가지 않도록 기둥을 옮겨가며 기둥 3번으로 모든 디스크 옮기기

 

#include <stdio.h>

//재귀함수
void hanoi(int n, char src, char dest, char temp){

		//디스크 옮기기
        if(n > 0){
                hanoi(n-1, src, temp, dest);
                printf("disk #%d : %c --> %c\n", n, src, dest);
                hanoi(n-1, temp, dest, src);
        }

}

int main(int argc, char *argv[]){
        int n;
        hanoi(4, 's', 'd', 't');

        return 0;
}

* 솔직히 그림을 그려보거나 실제 도형으로 하면 한 번에 이해될 거라고 생각합니다.. 

 

<콘솔 창>

하노이 타워

 

 

 

감사합니다!