재귀 알고리즘

mangez_js·2025년 2월 15일

자료구조

Study

목록 보기

46/47

재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 합니다

1은 자연수입니다.

자연수 n의 바로 다음 정수도 자연수입니다.

팩토리얼 구하기

0 != 1
n > 0이면 n! = n X (n-1)!

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);
        
        int x = stdIn.nextInt();
        
        System.out.println(factorial(x));
    }
}

매개변수 n에 전달받은 값이 0보다 클 때 : n * factorial(n-1)
매개변수 n에 전달받은 값이 0보다 크지 않을 때 : 1
return (n > 0) ? n * factorial(n - 1) : 1;

유클리드 호제법

두 정수의 최대공약수를 재귀적으로 구하는 방법

class EuclidGCDP
	static int gcd(int x, int y){
    	if(y == 0)
        	return x;
        else
        	return gcd(y, x % y);
    }
    
    public static void main(String[] args){
    	Scanner stdIn = new Scanner(System.in);
        int x = stdIn.nextInt();
        int y = stdIn.nextInt();
        
        System.out.println(gcd(x, y)
    }
}