[자료구조와 함께 배우는 알고리즘 입문] 5. 재귀 알고리즘 (1)

1. 재귀 알고리즘의 기본

 

1-1. 재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 자기 자신을 사용해 정의하고 있을 때 재귀적이라고 한다.

 

 

1-2. 팩토리얼 구하기
팩토리얼(n!)은 1부터 n까지의 수를 모두 곱한 값을 구하는 것이다.

만약 5!을 한다면 5*4*3*2*1 = 120의 결과값이 나와야한다.

재귀를 이용해 팩토리얼을 구하는 함수는 다음과 같다.

static int factorial(int n){
        if(n==1){
            return 1;
        }
        return n*(factorial(n-1));
    }

만약 n이 1과 같으면 1을 반환시키고, 그렇지 않을 경우에는 n*을 factorial(n-1)과 계속 곱해주어 팩토리얼의 결과값을 반환시킬 수 있게 한다.

 

 

1-3. 유클리드 호제법

두 정수의 최대공약수를 재귀를 통해 구할 수 있는데, 정수를 직사각형의 두 변의 길이라고 생각하면서 해결할 수 있다.

정수 n, m이 있을 때  m을 n으로 나눈 나머지가 0이 될 때 까지 재귀함수를 돌리면 된다.

코드를 보는게 좀 더 이해에 도움이 될 듯....?

int euclidGCD(int n, int m){
        if(m==0){
            return n;
        }
        return euclidGCD(n,m%n);
    }