재귀 함수

재귀 함수

@2024.03.21

재귀란?

💡

함수가 자기 자신을 호출하는 방식

• 문제를 작게 나누고, 그 작은 문제들을 해결하여 전체 문제의 해결책을 구하는데 사용
  →
  분할 정복(divide adn conquer)

• 구성
  • 기저 조건 : 함수가 자기 자신을 더 이상 호출하지 않은 조건이 필요하다.
    →
    무한 루프에 빠지는 것을 방지
  • 재귀적 단계 : 자기 자신을 호출하는 부분
    → 분할 정복
    

1. 팩토리얼

package ch03;

import java.util.Scanner;

public class FactorialCalculator {
    // 재귀함수 이용
    static int conputeFactorial(int n){
        if(n > 0){
            return n * conputeFactorial(n-1);
        }else { // 기저조건 0! = 1
            return 1;
        }
    }
    // 반복문 이용
    static int conputeFactorial2(int n){
        int result = 1;
        while(n>0){
            result  *= n;
            n--;
        }
        return result;
    }

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

        System.out.print("계산 할 정수를 입력하세요 >>");
        int x = sc.nextInt();

        System.out.printf("%d의 팩토리얼 값은 >> %d \n", x, conputeFactorial(x));
        System.out.printf("%d의 팩토리얼 값은 >> %d \n", x, conputeFactorial2(x));
    }
}

• n이 만약 3이라면
  • 3 * conputeFactorial(3-1);
  • 3 * 2 * conputeFactorial(2-1);
  • 3 * 2 * 1 * conputeFactorial(1-1);
  • 3 * 2 * 1 * 1 = 6

2. 유클리드 호제법 ← 최대공약수

💡

두 수 A와 B(A>B)의 최대 공약수는 ‘A와 A-B의 최대공약수와 같다’라는 원리를 이용하여 최대 공약수를 구하는 방법

• 유클리드 호제법에는 두가지 변형이 존재
  • 뺄셈을 이용하는 방법
    • 두 수 중 큰 수에서 작은 수를 빼며, 이 과정을 두 수가 같아질 때까지 반복하며 최종적으로 남은 수가 두 수의 최대 공약수가 된다.
    • ex) 1071과 462의 최대 공약수를 구하라
      1. 두 수 중 큰 수에서 작은 수를 뺍니다:
         • 1071 - 462 = 609
      2. 남은 수(609)와 작은 수(462) 중에서 큰 수를 다시 구합니다:
         • 609 - 462 = 147
      3. 남은 수(147)와 작은 수(462) 중에서 큰 수를 다시 구합니다:
         • 462 - 147 = 315
      4. 남은 수(315)와 작은 수(147) 중에서 큰 수를 다시 구합니다:
         • 315 - 147 = 168
      5. 남은 수(168)와 작은 수(147) 중에서 큰 수를 다시 구합니다:
         • 168 - 147 = 21

    public class Main {
        public static void main(String[] args) {
            int a = 48;
            int b = 18;
            
            int gcd = findGCD(a, b);
            
            System.out.println("두 수의 최대 공약수: " + gcd);
        }
        
        // 최대 공약수를 구하는 메소드
        public static int findGCD(int a, int b) {
            while (a != b) {
                if (a > b)
                    a = a - b;
                else
                    b = b - a;
            }
            return a;
        }
    }
    

  • 나눗셈을 이용하는 방법(모듈로 연산)
    • A와 B(A>B)가 있을때, A를 B로 나눈 나머지를 구한 후, 다시 B와 이 나머지를 나누며,
      나머지가 0이 될때까지 반복
      
    • 나머지0이 되면 B가 두 수의 최대 공약수다.
    • ex) 1071과 462의 최대 공약수를 구하라
      • 1071%462 = 147 → 462%147 = 21 → 147%21 = 0 ⇒ 최대공약수는 21

    public class Main {
        public static void main(String[] args) {
            int a = 48;
            int b = 18;
            
            int gcd = findGCD(a, b);
            
            System.out.println("두 수의 최대 공약수: " + gcd);
        }
        
        // 최대 공약수를 구하는 메소드
        public static int findGCD(int a, int b) {
            while (b != 0) {
                int temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }
    }