[JAVA] 재귀 알고리즘(recursion)

재귀란?

☞어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 합니다.

---

팩토리얼 구하기

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

import java.util.Scanner;

public class Factorial {

	public static int factorial(int n) {
		if (n > 0)
			return n * factorial(n - 1);
		else
			return 1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("양의 정수를 입력하세요.");
		
		int x = sc.nextInt();
		System.out.println(x+"의 팩토리얼은 "+factorial(x));
	}

}



          /////결과////////
          양의 정수를 입력하세요.
          4
          4의 팩토리얼은 24
          ///////////////

 

유클리드 호제법으로 최대공약수, 최소공배수 구하기

 

최대공약수 : 두 자연수의 공통된 약수 중 가장 큰 수

최소공배수 : 두 자연수의 공통된 배수 중 가장 작은 수 : 두 자연수의 곱 / 최대공약수

 

정의 : 2개의 자연수  a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단 a>b),

a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.  

이 성질에 따라, b를 r로 나눈 나머지 r0를 구하고,

다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

 

따라서 아래와 같은 수식으로 나타낼 수 있습니다.

GCD(A,B) = GCD(B,A%B)
if A%B ==0 -> GCD =B
    else GCD(B,A%B)