재귀 알고리즘

재귀란?

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

 

대표적인 재귀 알고리즘 1 : 팩토리얼 구하기

package recursive;

import java.util.Scanner;

public class Factorial {

	//양의 정수 n의 팩토리얼을 반환합니다.
	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.print("팩토리얼을 구하고 싶은 양의 정수를 입력하세요 : ");
		int num = sc.nextInt();
		
		System.out.println(num + "의 팩토리얼은 " + factorial(num) + " 입니다.");
	}
}

 

대표적인 재귀 알고리즘 2 : 유클리드 호제법 (최대공약수 구하기)

package recursive;

import java.util.Scanner;

public class EuclidGCD {

	//정수 x, y의 최대공약수를 구하여 반환합니다.
	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 sc = new Scanner(System.in);
		
		System.out.print("정수를 입력하세요 : ");
		int x = sc.nextInt();
		System.out.print("정수를 입력하세요 : ");
		int y = sc.nextInt();
		
		System.out.println("최대공약수는 " + gcd(x,y) + " 입니다.");
	}
}