점화식과 재귀함수

점화식(Recurrence)

- 어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식

ex) 피보나치 수열

---

재귀함수

- 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식

재귀함수는 어떻게 보면 반복문이 된다. 자기 함수를 계속 호출하기 때문에.

반복문을 탈출하기 위한 종료 조건이 반드시 있어야 된다. 없으면 무한 루프에 빠짐

재귀함수는 점화식으로 나타낸 것을 굉장히 편리하게 풀어낼 수 있다.

---

실습 코드

// 기초 수학 - 점화식과 재귀함수

public class Main {

    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++) { // a1 = 3 x a0, an+1 = 3 x an
            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

// Practice1
// 팩토리얼을 재귀함수로 구현하시오.

public class Practice1 {

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

---

연습 코드2

// Practice2
// 최대공약수를 재귀함수로 구현하시오.

public class Practice2 {

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