점화식과 재귀함수 개념과 자바로 구현해보기

1. 점화식 (Recurrence)

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

       예시) 피보나치 수열

피보나치 수열

2. 재귀함수(Recursive Function)

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

재귀함수

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

- 점화식으로 해석

    recursion1(1) = 1

    recursion1(2) = recursion1(1) * 3

    recursion1(3) = recursion1(2) * 3

    recursion1(4) = recursion1(3) * 3

    

   즉, 정리하면 recursion(n) = recursion(n-1) * 3

   그러므로 재귀함수로 구현이 가능하다.