[JAVA] - 등차수열, 등비수열, 피보나치, 팩토리얼, 하노이탑 - 재귀와 반복

재귀와 반복을 이용하여 등차수열, 등비수열, 피보나치, 팩토리얼, 하노이탑 구하기 예제

1. 재귀

• 자신을 호출함으로써 문제를 해결하는 방식입니다.
• 문제를 부분 문제로 나누고, 부분 문제에 대해 동일한 알고리즘을 사용하여 해결하는 분할 정복법의 일종입니다.
• 종료 조건을 만족할 때까지 자신을 호출합니다.
• 함수 호출 스택에 추가 비용이 들어가기 때문에 과도한 재귀 호출은 스택 오버플로우를 유발할 수 있습니다.
• Top-Down 방식은 주로 재귀적인 접근 방식을 사용하며, 문제를 작은 문제로 쪼개고 결합하여 전체 문제으 해를 구합니다.

---

2. 반복

• 반복문을 사용하여 문제를 해결하는 방법입니다.
• 코드가 좀 더 복잡할 수 있으나, 스택 오버플로우 문제에 상대적으로 자유롭습니다.
• Bottom-Up 방식은 주로 반복적인 방식을 사용하고, 먼저 작은 문제를 해결하고 이를 이용해서 더 큰 부분 문제들을 점진적으로 해결하는 방식입니다.

---

등차수열 & 등비수열

• 등차수열 : 각 항이 이전 항에 일정한 값을 더한 수열입니다. 이 일정한 값을 공차라고 합니다.
• 등비수열 : 각 항이 이전 항에 일정한 값을 곱한 수열입니다. 이 일정한 값을 공비라고 합니다.
  • 등차 / 등비 구하기 예시

    package math;
    
    public class 등차_등비_수열 {
      public static void main(String[] args) {
        /*
        등차수열 (Arithmetic Sequence)
        정의: 등차수열은 각 항이 이전 항에 일정한 값을 더한 수열입니다. 이 일정한 값을 공차라고 합니다.
        등비수열 (Geometric Sequence)
        정의: 등비수열은 각 항이 이전 항에 일정한 값을 곱한 수열입니다. 이 일정한 값을 공비라고 합니다.
         */
    
        int firstTerm = 2;  // 첫 번째 항
        int commonDifference = 2;  // 공차, 공비
        int n = 5;  // 구하고자 하는 항의 개수
    
        System.out.println("-----------등차수열 구하기-----------");
        // 재귀적 방법
        System.out.println("-----------재귀-----------");
        arithmeticSequenceRecursion(firstTerm, commonDifference, n);
    
        // 반복적 방법
        System.out.println("\n-----------반복-----------");
        arithmeticSequenceRepetition(firstTerm, commonDifference, n);
    
        System.out.println("\n\n-----------등비수열 구하기-----------");
        // 재귀적 방법
        System.out.println("-----------재귀-----------");
        geometricSequenceRecursion(firstTerm, commonDifference, n);
    
        // 반복적 방법
        System.out.println("\n-----------반복-----------");
        geometricSequenceRepetition(firstTerm, commonDifference, n);
      }
    
      // 등차수열 재귀
      private static void arithmeticSequenceRecursion (int first, int diff, int n) {
        if (n == 0) {
          return;
        }
        System.out.print(first + " ");
        arithmeticSequenceRecursion(first + diff, diff, n - 1);
      }
    
      // 등차수열 반복
      private static void arithmeticSequenceRepetition (int first, int diff, int n) {
        for (int i = 0; i < n; i++) {
          System.out.print(first + i * diff + " ");
        }
      }
    
      // 등비수열 재귀
      private static void geometricSequenceRecursion (int first, int diff, int n) {
        if (n == 0) {
          return;
        }
        System.out.print(first + " ");
        geometricSequenceRecursion(first * diff, diff, n - 1);
      }
    
      // 등비수열 반복
      private static void geometricSequenceRepetition (int first, int diff, int n) {
        for (int i = 0; i < n; i++) {
          System.out.print(first + " ");
          first *= diff;
        }
      }
    }

---

피보나치

• 피보나치 수열 : 첫 번째 항과 두 번째 항은 1이며, 세 번째 항부터 바로 앞의 두 항을 더한 수열입니다.
  • 피보나치 수열 구하기 예시

    package math;
    
    public class 파보나치_수열 {
      public static void main(String[] args) {
        /*
        정의: 피보나치 수열은 첫 번째 항과 두 번째 항은 1이며,
        세 번째 항부터는 바로 앞의 두 항을 더한 수열입니다.
         */
    
        int n = 6;
        System.out.println("-----------파보나치 수열-----------");
        System.out.println("-----------재귀-----------");
        fibonacciRecursive(0, 1, n);
    
        System.out.println("\n-----------반복-----------");
        fibonacciIterative(0, 1, n);
      }
    
      // 재귀적 방법
      private static void fibonacciRecursive (int a, int b, int n) {
        if (n == 0) {
          return;
        }
        System.out.print(a + " ");
        fibonacciRecursive(b, a + b, n - 1);
      }
    
      // 반복적 방법
      private static void fibonacciIterative (int a, int b, int n) {
        int sum;
        for (int i = 0; i < n; i++) {
          System.out.print(a + " ");
          sum = a + b;
          a = b;
          b = sum;
        }
      }
    }

---

팩토리얼

• 팩토리얼 : 1부터 n까지의 모든 수를 곱한 값입니다.
  • 팩토리얼 구하기 예시

    package math;
    
    public class 팩토리얼 {
      public static void main(String[] args) {
        /*
        정의: 팩토리얼은 1부터 n까지의 모든 수를 곱한 값입니다.
        수학적으로 n! = n × (n-1) × ... × 1입니다.
         */
    
        int n = 5;
        int i = 1;
        System.out.println("-----------팩토리얼-----------");
        System.out.println("-----------재귀-----------");
        factorialRecursive(n, i);
    
        System.out.println("\n-----------반복-----------");
        factorialIterative(n, i);
      }
    
      // 재귀적 방법
      private static void factorialRecursive (int n, int i) {
        if (n == 0) {
          System.out.println(i);
          return;
        }
        i *= n;
        System.out.println(n + " 번째 : " + i);
        factorialRecursive(n - 1, i);
      }
    
      // 반복적 방법
      private static void factorialIterative (int n, int i) {
        for (int j = n; j >= 1; j--) {
          i *= j;
          System.out.println(j + " 번째 : " + i);
        }
        System.out.println(i);
      }
    }

---

하노이탑

• 하노이탑 : n개의 원반을 한 기둥에서 다른 기둥으로 옮기는 문제입니다. 한 번에 하나의 원반만 이동 가능하며 큰 원반이 작은 원반 위에 놓여서는 안 됩니다.
  • 하노이탑 구하기 예시

    package math;
    
    public class 하노이의_탑 {
      public static void main(String[] args) {
        /*
        정의: 하노이탑 문제는 n개의 원반을 한 기둥에서 다른 기둥으로 옮기는 문제로,
        한 번에 하나의 원반만 이동 가능하며 큰 원반이 작은 원반 위에 놓여서는 안 됩니다.
          1. 한 번에 하나의 원판만 이동할 수 있다.
          2. 큰 원판은 작은 원판 위에 놓을 수 없다.
          3. 모든 원판을 시작 기둥에서 목표 기둥으로 옮겨야 한다.
        */
    
        int n = 3;  // 원판의 개수
        System.out.println("-----------하노이의 탑-----------");
    
        System.out.println("-----------재귀-----------");
        hanoiRecursive(n, 'A', 'C', 'B');  // n개의 원판을 A 기둥에서 C 기둥으로 B 기둥을 사용하여 이동
    
        System.out.println("\n-----------반복-----------");
        hanoiIterative(n);  // 반복적 방법으로 하노이의 탑 문제 해결
      }
    
      // 재귀적 방법
      private static void hanoiRecursive(int n, char from, char to, char aux) {
        if (n == 1) {
          System.out.println("원판 1을 " + from + "에서 " + to + "으로 이동");
          return;
        }
        hanoiRecursive(n - 1, from, aux, to);  // n-1개 원판을 보조 기둥으로 이동
        System.out.println("원판 " + n + "을 " + from + "에서 " + to + "으로 이동");  // n번째 원판을 목표 기둥으로 이동
        hanoiRecursive(n - 1, aux, to, from);  // 보조 기둥에서 목표 기둥으로 n-1개 원판을 이동
      }
    
      // 반복적 방법
      private static void hanoiIterative(int n) {
        int totalMoves = (int) Math.pow(2, n) - 1;  // 총 이동 횟수 계산
        char from = 'A', to = 'C', aux = 'B';  // 기둥 이름
    
        // 짝수 개의 원판이 있는 경우, 시작 기둥과 목표 기둥을 바꿔야 함
        if (n % 2 == 0) {
          char temp = to;
          to = aux;
          aux = temp;
        }
    
        for (int i = 1; i <= totalMoves; i++) {
          int fromPeg = (i & i - 1) % 3;  // 이동할 기둥 계산
          int toPeg = ((i | i - 1) + 1) % 3;  // 이동할 목표 기둥 계산
          System.out.println("이동: 원판 " + (fromPeg + 1) + "을 " + getPegName(fromPeg) + "에서 " + getPegName(toPeg) + "으로 이동");
        }
      }
    
      // 기둥 이름을 반환하는 헬퍼 함수
      private static String getPegName(int peg) {
        switch (peg) {
          case 0: return "A";
          case 1: return "B";
          case 2: return "C";
          default: return "";
        }
      }
    }

---

전체코드

package math;

public class math {
  public static void main(String[] args) {
    /*
    등차수열 (Arithmetic Sequence)
    정의: 등차수열은 각 항이 이전 항에 일정한 값을 더한 수열입니다. 이 일정한 값을 공차라고 합니다.
    등비수열 (Geometric Sequence)
    정의: 등비수열은 각 항이 이전 항에 일정한 값을 곱한 수열입니다. 이 일정한 값을 공비라고 합니다.
     */

    int firstTerm = 2;  // 첫 번째 항
    int commonDifference = 2;  // 공차, 공비
    int n = 5;  // 구하고자 하는 항의 개수
    int i = 1;

    System.out.println("-----------등차수열 구하기-----------");
    System.out.println("-----------재귀-----------");
    arithmeticSequenceRecursion(firstTerm, commonDifference, n);

    System.out.println("\n-----------반복-----------");
    arithmeticSequenceRepetition(firstTerm, commonDifference, n);

    System.out.println("\n\n-----------등비수열 구하기-----------");
    System.out.println("-----------재귀-----------");
    geometricSequenceRecursion(firstTerm, commonDifference, n);

    System.out.println("\n-----------반복-----------");
    geometricSequenceRepetition(firstTerm, commonDifference, n);
    
    System.out.println("-----------파보나치 수열-----------");
    System.out.println("-----------재귀-----------");
    fibonacciRecursive(0, 1, n);

    System.out.println("\n-----------반복-----------");
    fibonacciIterative(0, 1, n);
    
    System.out.println("-----------팩토리얼-----------");
    System.out.println("-----------재귀-----------");
    factorialRecursive(n, i);

    System.out.println("\n-----------반복-----------");
    factorialIterative(n, i);
    
    System.out.println("-----------하노이의 탑-----------");
    System.out.println("-----------재귀-----------");
    hanoiRecursive(n, 'A', 'C', 'B');  // n개의 원판을 A 기둥에서 C 기둥으로 B 기둥을 사용하여 이동

    System.out.println("\n-----------반복-----------");
    hanoiIterative(n);  // 반복적 방법으로 하노이의 탑 문제 해결
  }

  // 등차수열 재귀
  private static void arithmeticSequenceRecursion (int first, int diff, int n) {
    if (n == 0) {
      return;
    }
    System.out.print(first + " ");
    arithmeticSequenceRecursion(first + diff, diff, n - 1);
  }

  // 등차수열 반복
  private static void arithmeticSequenceRepetition (int first, int diff, int n) {
    for (int i = 0; i < n; i++) {
      System.out.print(first + i * diff + " ");
    }
  }

  // 등비수열 재귀
  private static void geometricSequenceRecursion (int first, int diff, int n) {
    if (n == 0) {
      return;
    }
    System.out.print(first + " ");
    geometricSequenceRecursion(first * diff, diff, n - 1);
  }

  // 등비수열 반복
  private static void geometricSequenceRepetition (int first, int diff, int n) {
    for (int i = 0; i < n; i++) {
      System.out.print(first + " ");
      first *= diff;
    }
  }
  
  // 재귀적 방법
  private static void fibonacciRecursive (int a, int b, int n) {
    if (n == 0) {
      return;
    }
    System.out.print(a + " ");
    fibonacciRecursive(b, a + b, n - 1);
  }

  // 반복적 방법
  private static void fibonacciIterative (int a, int b, int n) {
    int sum;
    for (int i = 0; i < n; i++) {
      System.out.print(a + " ");
      sum = a + b;
      a = b;
      b = sum;
    }
  }
  
  // 재귀적 방법
  private static void factorialRecursive (int n, int i) {
    if (n == 0) {
      System.out.println(i);
      return;
    }
    i *= n;
    System.out.println(n + " 번째 : " + i);
    factorialRecursive(n - 1, i);
  }

  // 반복적 방법
  private static void factorialIterative (int n, int i) {
    for (int j = n; j >= 1; j--) {
      i *= j;
      System.out.println(j + " 번째 : " + i);
    }
    System.out.println(i);
  }
  
  // 재귀적 방법
  private static void hanoiRecursive(int n, char from, char to, char aux) {
    if (n == 1) {
      System.out.println("원판 1을 " + from + "에서 " + to + "으로 이동");
      return;
    }
    hanoiRecursive(n - 1, from, aux, to);  // n-1개 원판을 보조 기둥으로 이동
    System.out.println("원판 " + n + "을 " + from + "에서 " + to + "으로 이동");  // n번째 원판을 목표 기둥으로 이동
    hanoiRecursive(n - 1, aux, to, from);  // 보조 기둥에서 목표 기둥으로 n-1개 원판을 이동
  }

  // 반복적 방법
  private static void hanoiIterative(int n) {
    int totalMoves = (int) Math.pow(2, n) - 1;  // 총 이동 횟수 계산
    char from = 'A', to = 'C', aux = 'B';  // 기둥 이름

    // 짝수 개의 원판이 있는 경우, 시작 기둥과 목표 기둥을 바꿔야 함
    if (n % 2 == 0) {
      char temp = to;
      to = aux;
      aux = temp;
    }

    for (int i = 1; i <= totalMoves; i++) {
      int fromPeg = (i & i - 1) % 3;  // 이동할 기둥 계산
      int toPeg = ((i | i - 1) + 1) % 3;  // 이동할 목표 기둥 계산
      System.out.println("이동: 원판 " + (fromPeg + 1) + "을 " + getPegName(fromPeg) + "에서 " + getPegName(toPeg) + "으로 이동");
    }
  }

  // 기둥 이름을 반환하는 헬퍼 함수
  private static String getPegName(int peg) {
    switch (peg) {
      case 0: return "A";
      case 1: return "B";
      case 2: return "C";
      default: return "";
    }
  }
}