점화식과 재귀함수

점화식과 재귀함수

점화식 (Recurrence)

어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식
예시) 피보나치 수열
1, 1, 2, 3, 5, 8, 13, …
F1 = F2 = 1, Fn+2 = Fn+1 + Fn

재귀함수

어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식
반환타입 함수이름 (매개 변수) {
종료 조건
…
함수이름(…)
}

public class Practice5 {

    static int recursion1(int n) {
        if (n == 1) {
            return 1;
        }
        return 3 * recursion1(n - 1);
    }

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

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

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


        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;
                a2 = result;
            }
        }
        System.out.println(result);
    }
}

== 점화식/재귀함수 연습1 ==
27
== 점화식/재귀함수 연습2 ==
15
== 점화식/재귀함수 연습3 ==
8

public class Practice5_1 {

    static  int factorial(int n){
        if(n == 1){
            return 1;
        }
        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));
    }
}

1
2
6
24
120

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


    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));
    }
}

1
2
4

출처 : 제로베이스