5-1. 재귀의 기본(Recursive)

재귀(Recursive)

: 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용해 정의될 때 재귀적(recursive)이라고 한다. 재귀를 사용하면 프로그램도 간결하게 할 수 있다.

 

재귀적 정의(recursive definition) 예:

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

 

 

 

 

 

・팩토리얼 구하기

 

-음이 아닌 정수 n의 팩토리얼(n!)

1. 0! = 1
2. n > 0 이면 n! = n x (n - 1)!

 

 

 

public class Factorial {
    
    static int factorial(int n) {
        if(n > 0)
            return n * factorial(n - 1);
        else
            return 1;
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("정수 입력: ");
        int x = stdIn.nextInt();
        
        System.out.println(x + "의 팩토리얼: " + factorial(x));
    }
}

 

 

 

 

 

※직접 재귀와 간접 재귀

 

-직접 재귀: 메서드 내부에서 자신과 같은 메서드를 호출

-간접 재귀: 메서드 a가 메서드 b를 호출, 메서드 b가 다시 메서드 a를 호출하는 구조로 다른 메서드를 통해 자신과 같은 메서드를 간접적으로 호출한다.

 

 

 

 

 

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

: 두 정수의 최대공약수(greatest common divisor)를 구하는 알고리즘 중 하나

 

두 정수 x, y의 최대공약수 => gcd(x, y)

x = az, y = bz를 만족하는 정수 a, b와 최대의 정수 z가 존재할 때, z를 gcd(x, y)라고 할 수 있다.

=> 최대공약수는 ①y가 0이면 x, ②y가 0이 아니면 gcd(y, x % y)

 

 

 

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