[Algorithm] C - 재귀함수(Recursion)

재귀(Recursive)란

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적 이라고 한다.
쉽게 말해서 자기 자신을 포함한 것이라고 쉽게 생각할 수 있다.

프로그래밍에서 재귀란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 말한다.
재귀를 효과적으로 사용하면 프로그램을 간결하게 작성할 수 있다.

재귀적 정의에 의해 무한으로 존재하는 자연수를 아래의 두 조건으로 정의할 수 있다.

• 1은 자연수이다.
• 자연수 n의 바로 다음 수도 자연수이다.

팩토리얼(Factorial)

팩토리얼이란 한글로 계승 또는 순차곱셈이라고 하며, 1에서 시작하여 어떤 범위에 있는 모든 정수를 곱하는 것을 의미한다.
팩토리얼 예제는 재귀함수의 예제로 많이 사용한다.

#include 

int Factorial(int n);

int main()
{
    int n;
    printf("정수를 입력하세요 : ");
    scanf("%d", &n);
    
    printf("%d의 Factorial 값은 %d 입니다.\n", n, Factorial(n));
    
    return 0;
}

int Factorial(int n)
{
    if(n > 0) {
        return n * Factorial(n - 1);
    }
    else {
        // 마지막 호출일 때
        return 1;
    }
}

팩토리얼의 표기식은 숫자 뒤에 !를 붙여 표시한다.
예를 들어, 10의 팩토리얼인 10!은 10 * 9!로 구할 수 있고, 표시할 수 있다.

3을 매개변수로 받은 팩토리얼 함수 호출 과정

A : Factorial(3)을 실행하면 3 * Factorial(2)를 반환하는데, 이 값을 구하기 위해 다시 2를 매개변수로 주고 Factorial 함수를 호출한다.

B : 호출된 함수는 매개변수 n에 2를 전달받고, 다시 2 * Factorial(1)을 수행하기 위해 Factorial 함수를 호출한다.

C : 다시 호출된 Factorial 함수는 매개변수 n에 1을 전달받고, 1 * Factorial(0)을 수행하기 위해 Factorial 함수를 호출한다.

D : 마지막으로 호출된 Factorial 함수는 매개변수 n에 전달받은 값이 0이므로 1을 반환한다.

마지막 함수 호출 후, 다시 C - B - A 순서로 역순으로 실행된다.

유클리드 호제법(Euclidean method of mutual division)

유클리드 호제법은 두 정수의 최대공약수를 재귀적으로 구하는 방법을 말한다.
두 정수의 최대공약수를 구하는 문제는 아래 문제처럼 바꿀 수 있다.

직사각형을 정사각형으로 완전히 채울 때 만들 수 있는 정사각형의 가장 긴 변의 길이 구하기

아래 그림은 문제 풀이에 관한 설명이다.

1. 22 x 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 생각하는 정사각형으로 분할한다. 이 경우 8 x 8 크기의 정사각형 2개, 8 x 6 크기의 직사각형 1개가 남는다.
2. 은 8 x 6 크기의 직사각형으로 다시 같은 과정을 수행한다. 그러면 6 x 6 크기의 정사각형 1개, 6 x 2 크기의 직사각형 1개가 남는다.
3. 다시 남은 6 x 2 크기의 직사각형으로 같은 과정을 수행한다. 그 후 2 x 2 크기의 정사각형 3개로 나눌 수 있는데, 여기서 얻은 2가 최대 공약수이다.

위 과정처럼 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지는 가장 작은 값이 최대 공약수이다.

나누어지지 않을 경우 나누어떨어질 때 까지 같은 과정을 재귀적으로 반복한다.

#include <stdio.h>

int GCD(int x, int y);

int main() 
{
    int x, y;
    printf("정수를 입력하세요 : ");
    scanf("%d", &x);
    printf("정수를 입력하세요 : ");
    scanf("%d", &y);
    printf("최대 공약수는 %d 입니다.\n", GCD(x, y));

    return 0;
}

int GCD(int x, int y)
{
    if(y == 0) {
        return x;
    }
    else {
        return GCD(y, x % y);
    }
}

https://github.com/JeHeeYu/Algorithm/tree/main/Recursion

GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이

 

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편