[자료구조] #1 재귀호출

재귀호출

컴퓨터 과학에서 재귀(Recursion)란, 자기 자신을 재참조하는 방법을 뜻하며, 재귀호출의 형태로 사용됩니다.

 

문제 해결 알고리즘에 있어서 문제를 작은 단위로 분해하는 것은 알고리즘을 작성하는 데 필요한 요소입니다. 재귀호출은 문제의 작은 단위가 자기 자신으로 이루어져 있을 때 주로 사용합니다.

 

재귀호출은 알고리즘 속에 자기 자신을 포함하는 형태일 때 주로 사용되는데, 팩토리얼의 예시를 통해 재귀호출을 조금 더 알아보겠습니다.

 

 

 

팩토리얼(!)

팩토리얼(!)의 정의

n에 대한 팩토리얼(!)은 다음과 같이 정의합니다.

 

n! = n * (n-1) * (n-2) * ... 3 * 2 * 1

 

이를 다시 정의하면 다음과 같이 재귀적으로 정의할 수 있습니다.

 

n! = n * (n-1)!

 

이와 같이 n!를 구하려면 (n-1)!을 구해야 하고, (n-1)!을 구하려면 또 다시 (n-2)!을 구해야 합니다.

 

이렇게 알고리즘 속에 자기 자신을 재참조하는 방법을 재귀라고 부르며, 팩토리얼은 재귀의 가장 간단한 예시입니다.

 

 

 

팩토리얼(!) 알고리즘 종료조건

재귀에서 가장 중요한 것은 "언제 재귀가 끝나는가?" 입니다.

이는 다른 말로 종료 조건이라고 말할 수 있는데요.

 

팩토리얼의 경우에 종료 조건은 다음과 같습니다.

 

n = 1일 경우, 즉 1!

 

이것이 종료 조건에 해당합니다.

 

 

 

C언어로 구현한 팩토리얼

팩토리얼 알고리즘을 재귀호출 방법으로 코딩해보겠습니다.

 

#include <stdio.h>

long int fact(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * (n - 1);
    }
}

int main(void) {
    printf("%d", fact(5));

    return 0;

}

 

실행 결과를 보면, 5! 결과인 20이 정상적으로 출력되는 것을 확인할 수 있습니다.

 

 

 

피보나치 수열

피보나치 수열의 정의

피보나치 수열의 정의 또한 재귀적으로 이루어져 있으므로 재귀호출을 통해 구현할 수 있습니다.

 

F(0) = 0 F(1) = 1 F(n+2) = F(n+1) + F(n)

 

피보나치 수열은 제0항은 0, 제1항은 1으로 정의한 다음, 2항부터는 바로 직전의 두 항을 더하여 계산합니다.

 

즉, 제3항 = 제0항+제1항 = 0 + 1 = 1입니다.

 

 

 

피보나치 수열 알고리즘의 종료조건

앞서 재귀호출에서 중요한 것은 종료조건이라고 말한 바 있습니다.

 

피보나치 수열의 경우, 차례대로 생각해보면 맨 마지막에는 제0항과 제1항이 필요하다는 것을 알 수 있습니다.

 

따라서 F(0), F(1)이 종료조건입니다.

 

 

 

C언어로 구현한 피보나치 수열

피보나치 수열을 재귀호출 방법으로 코딩해보겠습니다.

 

#include <stdio.h>

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

int main(void) {
    printf("%d", fibonacci(10));
    return 0;
}

 

피보나치 수열을 제0항부터 제9항까지 나열해보면 다음과 같습니다.

 

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

 

따라서 제10항은 21+34 = 55이고, 실행 결과 역시 55입니다.