재귀함수

<기본코드>

public class Chap_05 {
    static int recursion1(int n) {
        if (n == 1) {
            return 1;
        }

        return 3 * recursion1(n - 1);
        /*
        n = 4
        return 3 * recursion1(n - 1); 호출
        3 x recursion1(3)
        3 x recursion1(2)
        3 x recursion1(1)

        3 x return 1

        3, 9, 27
         */
    }

    static int recursion2(int n){
        if (n == 1){
            return 1;
        } else {
            return n + recursion2(n-1);
        }
    }

    static int recursion3(int n){
        if (n < 3){
            return 1;
        } else {
            return recursion3(n-2) + recursion3(n-1);
        }
    }

    /*
    n = 6
    recursion3(4) + recursion3(5)
    recursion3(4) = recursion3(2) + recursion3(3)
    recursion3(3) = recursion3(1) + recursion3(2)

    recursion3(5) = recursion3(3) + recursion3(4)
    recursion3(4) = recursion3(2) + recursion3(3)
    recursion3(3) = recursion3(1) + recursion3(2)
     */

    public static void main(String[] args) {

//      점화식 -> 반복문, 재귀함수
        System.out.println("== 점화식/재귀함수 연습1 ==");
//      1, 3, 9, 27, ... 의 n번째 수
        int n = 4; //4번째 수
        int result = 1;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                result = 1;
            } else {
                result *= 3;
            }
        }
        System.out.println(result); // n번째수 출력

        /*
        a1 = 3 x an
        an+1 = 3 x an
         */

        System.out.println("== 점화식/재귀함수 연습2 ==");
//      1, 2, 3, 4, 5, 6, ... 의 n번째 까지의 합
        n = 5;
        result = 0;
        for (int i = 1; i < n + 1; i++) {
            result += i;
        }
        System.out.println(result);


        System.out.println("== 점화식/재귀함수 연습3 ==");
//      1, 1, 2, 3, 5, 8, 13, ...의 n번 째 수
        n = 6;
        result = 0;
        int a1 = 1;
        int a2 = 1;

        if (n < 3) {
            result =1;
        } else {
            for (int i = 2; i < n; i++) {
                result = a1+ a2;
                a1 = a2;
                a1 = result;
            }

            System.out.println("result = " + result);
        }
    }
}

<연습문제>
(1)

public class Practice_05 {
    static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

    public static void main(String[] args) {
//      Test code
        System.out.println(factorial(1));
        System.out.println(factorial(2));
        System.out.println(factorial(3));
        System.out.println(factorial(4));
        System.out.println(factorial(5));
    }
}

(2)

// Practice2
// 최대공약수를 재귀함수로 구현하시오.
public class Practice_06 {
    static int gcd(int a, int b){
        if (a % b ==0){
            return b;
        } else {
            return gcd(b, a%b);
        }
    }

    /*
    만약 gcd로 3과 5가 넘어오면,
    처음 3을 5로 나눈 나머지가 0이 되지 않으니, return gcd(b, a%b) 실행
    gcd(5, 3) -> gcd(3, 2) -> gcd(2, 1)
    // 0이 나올때 값이 최대 공약수

    gcd(5,3)
     */

    public static void main(String[] args) {
//      Test code
        System.out.println(gcd(3, 5));
        System.out.println(gcd(2, 6));
        System.out.println(gcd(8, 12));
    }
}