재귀(Recursion)란?

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

해당 알고리즘을 이해하려면 절차지향적 사고를 귀납적 사고로 전환시켜야한다.

절차지향적 사고의 예시

1. 문제: 1부터 5까지의 합을 구하라.
2. 절차:
   • 변수 sum을 0으로 초기화한다.
   • 변수 i를 1로 초기화한다.
   • i가 5 이하일 때까지 다음을 반복한다:
     • sum에 i를 더한다.
     • i를 1 증가시킨다.
   • 최종적으로 sum을 반환한다.

귀납적 사고의 예시

1. 문제: 1부터 5까지의 합을 구하라.
2. 귀납적 사고:
   • 기본 사례: 1부터 1까지의 합은 1이다.
   • 재귀 사례: 1부터 n까지의 합은 n + (1부터 n-1까지의 합)이다.

재귀코드의 조건

• 기본조건(Base case): 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.
• 기본 조건으로 수렴: 모든 입력은 기본 조건으로 수렴해아 한다.

해당 조건을 지키지 못하면 코드는 무한히 순환되게 된다.

재귀 코드의 정보

• 재귀 함수를 명확히 정의할 것!!
  • 어떤 인자를 받을지 정의
  • 어디까지 계산하고 재귀 함수로 돌려줄지 정의
• 모든 재귀 함수는 반복문으로 구현할 수 있음!
  • 재귀 함수가 코드는 간결해 보이지만 메모리&시간 손해를 볼 수 있으니 유의할 것 → 재귀는 비용이 아주 크다.
    
  • 재귀 없이 구현을 하게 될 경우 너무 코드가 복잡해질 때 재귀로 구현하는 게 좋음

구현 예시

1. 피보나치 함수

   초항 2개가 1,1이고 그 뒤의 항은 직전 항 2개의 합으로 정의되는 함수.

   예시 ) 1, 1, 2, 3, 5, 8, 13, …

   // 구현
   public static int fib(int n){
       if(n <= 2){
         return 1;
       }
       return fib(n-2) + fib(n-1);
   }

   해당 함수의 시간복잡도는 n의 지수승이 된다.

   왜냐하면 자신이 이미 계산한 함수를 또다시 계산하는 과정에서 시간이 소요되기 때문.

   dp로 구현하면 O(n)으로 구현 가능

     static int[] dp = new int[100];
   
     public static int fibDP(int n) {
       if (n < 2) {
         return 1;
       }
       if (dp[n] != 0) {
         return dp[n];
       }
       return dp[n] = fibDP(n - 1) + fibDP(n - 2);
     }

   2개 이상 재귀함수가 들어가는 경우 한번 계산한 조항을 또한번 계산할 수 도 있기에 유의할 것!
   -> 해당 경우에는 DP 사용을 고려할 것.

2. boj_1629 곱셈 문제

   a^b mod m 를 구하는 함수.

   public static int powerMod(int a, int b, int m){
       // a^b mod m 구하기
       int val = 1;
       while(b-- == 0){
         val *= a;
       }
       return val % m;
     }

   해당 함수는 O(b) 시간복잡도를 가지는 함수

   하지만 해당 함수는 int Overflow가 발생하여 2^31 이상의 양수가 들어오면 옳은 값을 호출하지 못한다.

   사실 m으로 나눈 나머지를 구하는 것이므로 우리는 곱한 전체 값이 필요한 것은 아니다.

   그러므로 높은 값이 나오더라도 진행할 수 있게 long으로 변형해준다.

   public static int powerMod(long a, long b, long m){
       // a^b mod m 구하기
       long val = 1;
       while(b-- == 0){
         val *= a;
       }
       return val % m;
     }

   이렇게 진행하면 우리는 a^b mod m 을 O(b) 시간 복잡도로 구할 수 있게 된다.

   하지만 b 가 2^31(약 20억) 이상이라 시간 복잡도 내에서 해결할 수 없을 경우는 어떡할까?

   그럴땐 해당 성질을 사용하면 된다.

   $2^{5}\mod{3} \equiv 2 \ 가\ 주어졌을\ 때, 2^{10}\mod{3} 을 \ 구해라. \\ 2^{5*2}\mod{3} \equiv (2^5 \mod{3})^2 \mod3 \\ 2^{5*2}\mod{3} \equiv 2^2 \mod3 \\ 2^{5*2}\mod{3} \equiv 1$

   그렇다면 이제 해당 원리로 귀납법을 도출해보자.

   1. a^1 mod m 을 구할 수 있다.
   2. a^(k) mod m 를 계산했으면 a^(2k)와 a^(2k+1) 도 O(1)에 계산할 수 있다.
      • a^(2k+1) 는 a^(2k) 를 계산하고 a 를 한번만 곱해주면 된다.

   왜 $a^{2k}$ 를 사용하는가?

   거듭 제곱 알고리즘에서는 $b$ 의 이진 표현을 사용하여 빠르게 계산합니다. 이진 표현을 사용하면 지수를 반으로 줄일 수 있고, 따라서 시간 복잡도를 크게 줄일 수 있습니다. 이 알고리즘의 핵심 아이디어는 다음과 같습니다:

   1. 짝수 지수: $b$ 가 짝수일 때,

      $a^b = (a^{b/2})^2$

      예를 들어, $a^{10} = (a^5)^2$

   2. 홀수 지수: $b$가 홀수일 때,

      $a^b = a \cdot a^{b-1}$

      예를 들어, $a^{11} = a \cdot a^{10}$

   이를 통해 $b$ 를 절반으로 줄이면서 계속 계산할 수 있습니다. 결과적으로, 각 단계에서 지수를 절반으로 줄여가며 계산하기 때문에 시간 복잡도는 $O(\log b)$가 됩니다.

   private static long powerMod(long a, long b, long m) {
       long result;
       if(b == 1){
         return a % m; // a^1 % m
       }
       result = powerMod(a, b/2, m); // 2를 나누어 재귀함수를 호출시킨다.
       result = result * result % m; // 짝수라면 result = a^2 % m
       if(b % 2 == 1){ // 홀수라면
         return result * a % m; // a^2 * a % m
       }
       return result;
     }

🎯 결론.

결국 재귀 함수는 아래 수도코드로 일반화 할 수 있을 것 같다.

재귀함수(입력 매개변수):
    # 기본 사례(Base Case)를 확인합니다.
    만약 기본 사례에 해당하는 조건이라면:
        기본 사례에 대한 결과를 반환합니다.
    
    # 재귀 사례(Recursive Case)를 처리합니다.
    작은 부분 문제로 문제를 나눕니다.
    
    # 재귀 호출을 사용하여 작은 부분 문제를 해결합니다.
    작은 부분 문제들의 결과를 결합하여 전체 문제를 해결합니다.
    
    결과를 반환합니다.

문제 이해→ 기본 사례 설정 → 재귀 사례 정의