[알고리즘 독학] 재귀 알고리즘(1) 재귀의 기본

재귀의 기본

재귀적 : 어떤 사건이 자기 자신을 포함하고 다시 자가 자신을 사용하여 정의될 때

 

팩토리얼 구하기

1. 0! = 1

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

 

package search;

import java.util.Scanner;

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.print("정수를 입력하세요 : ");
		int x = stdIn.nextInt();
		
		System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
	}

}

 

 

 

유클리드 호제법

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

 

package search;

import java.util.Scanner;

public class EuclidGCD {
	
	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);
		
		System.out.println("두 정수의 최대공약수를 구합니다.");
		
		System.out.print("정수를 입력하세요 : "); int x = stdIn.nextInt();
		System.out.print("정수를 입력하세요 : "); int y = stdIn.nextInt();
		
		System.out.println("최대공약수는 " + gcd(x, y) + "입니다.");
		
	}

}