[재귀알고리즘]재귀 함수

1. 재귀란?

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

여기서 어떤 사건이 자기 자신을 포함하고,
다시 자기 자신을 사용하여 정의된다는 것을 "자연수 n(자기 자신)의 바로 다음 수도 자연수"로 볼 수 있다.

 

2. 팩토리얼 구하기

▶︎ 음이 아닌 정수의 팩토리얼(factorial) 구하기

package com.study.Algorithm;
import java.util.Scanner;
// 팩토리얼을 재귀적으로 구현

class Factorial {
	// 양의 정수 n의 팩토리얼을 반환합니다.
	static int factorial(int num) {
		if (num > 0) {
			return num * factorial(num - 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) + "입니다.");
	}
}

• factorial 메소드
  호출 시 전달된 파라미터 num이 0보다 크다면, num * factorial(num-1)을 반환하고, 호출 시 전달된 파라미터 num이 0보다 작거나 같다면 1을 반환한다. 이때 if문에 의해 factorial 메소드 안에서 다시 factorial 메소드가 호출되는데, 이것을 재귀 호출이라고 한다.

재귀 호출은 '메서드 자기 자신'을 호출하는 것이라고 이해하기 보다는 **'자기 자신과 똑같은 메서드'**를 호출한다고 이해하자.
즉, 복제된 자기를 호출하는 것이다.

 

▶︎ 직접 재귀
자기 자신이 다시 자기 자신과 같은 메소드를 호출하는 경우: a → a → a → ... → a

https://jwlee010523.tistory.com/entry/함수의-재귀적-호출의-이해

▶︎ 간접 재귀
메소드 a가 b를 호출하고, 호출된 b가 다시 a를 호출하는 경우: a → b → a → b → ... → a → b → a

 

3. 유클리드 호제법

• 주어진 두 수의 최대공약수를 재귀적으로 구하는 알고리즘을 말한다.
• 주어진 두 수를 직사각형으로 표현하여 가장 작은 정사각형을 만드는것이 알고리즘의 핵심 풀이 방법이다.
  
  

package com.study.Algorithm;
import java.util.Scanner;
// 유클리드 호제법으로 최대공약수 구하기

class EuclidAlgorithm {
	// 정수 x, y의 최대공약수를 구하여 반환합니다. 
	
	static int greatestCommonDivisor(int x, int y) {
		if (y == 0) {
			return x;
		} else {
			int arguX = y;
			int arguY = x % y;
			return greatestCommonDivisor(arguX, arguY);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("두 정수의 최대공약수를 구합니다.");

		System.out.print("정수를 입력하세요：");
		int x = sc.nextInt();
		
		System.out.print("정수를 입력하세요：");
		int y = sc.nextInt();

		System.out.println("최대공약수는 " + greatestCommonDivisor(x, y) + "입니다.");
	}
}

1. 메인 메소드를 통해 정수를 2개 받아 greatestCommonDivisor 메소드에 전달해준다.
2. 전달받은 정수 x, y 중 y가 0이라면 x를 최대공약수로 리턴한다.
3. y가 0이 아니라면, y와 arguY의 값을 argument(인자)로 하여 다시 greatestCommonDivisor 메소드를 호출한다.
4. 3을 반복하여 arguY의 값이 0이 될 때까지 반복한다.
5. arguY의 값이 0일 때, argument로 함께 전달된 arguX의 값이 최대공약수가 된다.

 

자료출처: www.notion.so/4cdf3d96841c4ab1845c720026fbbb17