[재귀 알고리즘] 재귀 알고리즘 분석

재귀의 개념

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

 

■ 팩토리얼 구하기

재귀의 사용 예

음이 아닌 정수의 팩토리얼 구하는 프로그램

0! = 1

[예제] = 3!= 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1

public class Factorial {

    public static void main(String[] args) {
        int i = 3;
        System.out.println("factorial : " + factorial(i));
    }

    static int factorial(int n){
        if(n > 0){
            return n * factorial(n-1);
        }else{
            return 1;
        }
    }
}

■ 유클리드 호제법(Euclidean method of mutual division)

두 정수의 최대공약수 구하기

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) {
        System.out.println("gcd : " + gcd(2,7));
    }
}

■ 재귀적 표현

import java.util.Scanner;
import java.util.Stack;

public class Recur {
    static void recur(int n) {
        if (n > 0) {
            recur(n - 1);
            System.out.println(n);
            recur(n - 2);
        }
    }

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

        System.out.println("정수를 입력하세요");
        int x = scanner.nextInt();

        recur(x);
    }
}

■ 스택을 사용하여 비재귀적 구현

import java.util.Scanner;
import java.util.Stack;

public class NotRecur {

    static void notRecur(int n){
        Stack<Integer> stack = new Stack();

        while (true){
            if(n > 0){
                stack.push(n);  //임시 저장
                n = n - 1;
                continue;
            }

            if(!stack.isEmpty()){
                n = stack.pop();
                System.out.println(n);
                n = n-2;
                continue;
            }
            break;
        }
    }

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

        System.out.println("정수를 입력하세요");
        int x = scanner.nextInt();

        notRecur(x);
    }
}