1. 점화식(Recurrence Relation)이란?

점화식은 수열의 각 항이 그 이전 항들의 값에 의해 정의되는 관계식을 의미합니다. 간단히 말해, 이전 항들의 값을 사용하여 다음 항의 값을 구하는 방법을 나타냅니다.

1, 1, 2, 3, 5, 8, 13, …
$F_1\ =\ F_2\ =\ 1,\ F_{n+2}\ =\ F_{n+1} +\ F_n$

2. 재귀함수(Recursive Function)란?

재귀함수는 함수가 자신을 호출하는 것을 허용하는 함수입니다. 즉, 함수가 자신의 정의 내에서 자신을 호출하는 방법을 의미합니다.

반환타입 함수이름(매개 변수){
	종료 조건
	...
	함수이름(...)
}

3. 점화식과 재귀함수의 관계

점화식과 재귀함수는 서로 밀접하게 관련되어 있습니다. 실제로, 점화식은 종종 재귀함수의 형태로 구현됩니다. 이전에 설명한 피보나치 수열의 경우가 그 예시입니다.

재귀함수를 사용하여 점화식을 구현하는 것은 종종 코드를 더 간결하고 이해하기 쉽게 만들어 줍니다. 하지만 재귀함수는 재귀 호출에 따른 추가적인 메모리와 계산 비용이 발생할 수 있으므로, 항상 적절한 조건과 기저 사례를 고려하여 구현해야 합니다.

자바 코드 예시

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++) {
            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);


    }
}

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

public class Practice1 {

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

    public static void main(String[] args) {
        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));
    }
}

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

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) {
        System.out.println(gcd(3, 5));
        System.out.println(gcd(2, 6));
        System.out.println(gcd(8, 12));
    }
}