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

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

팩토리얼 구하기

class Factorial{
//10! = 10 * 9!
	static int factorial(int n){
    
    	if(n>0) return n*factorial(n-1);
        else return 1;
        
        }
}
      

유클리드 호제법

두 정수의 최대공약수를 재귀적으로 구하는 법
최대공약수 -> y가 0이면 x, y가 0이 아니면 gcd(y,x%y)

class euclidGCD{
	static int gcd(int x, int y){
    	if(y==0) return x;
        //몫이 0일때 
        else return gcd(y,x%y);
}

재귀 메서드 없는 factorial

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        int result = 1;

        for(int i=1;i<=number;i++){
            result*=i;
        }

        System.out.println(result);
    }
}

재귀 메서드 없는 GCD

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int result = 1;

        while(result>0){
            result = x % y;
            x=y;
            y=result;
        }
        System.out.println(x);
    }
}

static int gcdArray(int [] a)

import java.util.Scanner;

// 답지 보고 풀었음
// 배열의 모든 요소의 최대공약수 구하는 법
// 최대공약수 1, 배열 요소 1 

public class Main {
    public static int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    public static int gcdArray(int[] a, int start, int num) {
        if (num == 1) // 내용물이 하나라면 
            return a[start];
        else if (num == 2) // 내용물이 두개라면 
            return gcd(a[start], a[start + 1]);
        else // 내용물이 여러개면, 2개로 줄여야함
            return gcd(a[start], gcdArray(a, start + 1, num - 1));
    }
}

재귀 알고리즘 분석

하향식 분석 ㅣ 가장 위쪽에 있는 것부터 호출해 계단식으로 자세히 조사하는 분석기법 . 꼭대기부터 분석하면 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 반드시 효율적이다 라고는 할 수 없음

상향식 분석 ㅣ 아래쪽부터 쌓아 올리며 분석하는 방법

재귀 -> 비재귀
재귀 호출을 제거하기 위해서는 변수 n의 값을 '잠시' 저장해야한다. 이런 문제를 해결할 수 있는 데이터 구조 : stack

static void recur(int n){
    Intstack s = new Intstack(n);
    
    while(true){
        if(n>0){
            s.push(n); //n값 푸시
            n=n-1;
            continue;
        }
        if(s.isEmpty()!=true){
            n=s.pop();
            System.out.println(n);
            n=n-2;
            continue;
        }
        break;
    }
}