재귀 알고리즘

재귀 알고리즘(Recursion)은 함수가 자기 자신을 호출하는 것으로
이것은 문제를 더 작은 부분으로 나누어 해결하는 방식으로 동작하게 된다.

• 재귀 알고리즘에서 가장 중요한 것은 자기 자신을 무한히 호출하지 않도록 탈출 구문이 반드시 포함되어야 한다는 것이다.

💦 팩토리얼

  <구현>

---

  def factorial(num):
      if num > 0:
          return num * factorial(num - 1)
      else:
          return 1

  print(f'10! : {factorial(10)}') # 3628800

---

💦 피보나치 수열

• 앞에 있는 두 수를 더해서 현재의 수를 만들어가는 수열로 재귀 형태를 띠는 대표적인 수열이다.
  [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... ]
  

  <구현>

---

  def fibonacciRecursion(n):
      if n == 1: return 0
      elif n == 2: return 1
      else:
          return fibonacciRecursion(n-2) + fibonacciRecursion(n-1)

---

💦 유클리드 호제법

  <구현>

---

def euclidGCD(n1, n2):

    if n1 % n2 == 0: return n2
    else:
        return euclidGCD(n2, n1 % n2)

---

💦 하노이의 탑

• 게임의 일종으로 세 개의 기둥을 이용해서 원판을 다른 기둥으로 옮기는 것이다.
  단, 다음 제약 조건을 만족해야 한다.
  • 한 번에 한개의 원판만 옮길 수 있다.
  • 큰 원판이 작은 원판 위에 있어서는 안 된다.

  <구현>

---

  # 목적: 원반 n개를 from막대에서 to막대로 이동
  def moveDisc(discCnt, fromBar, toBar, viaBar):

      if discCnt == 1:
          print(f'{discCnt}번 disc: {fromBar}막대에서 {toBar}막대로 이동!')

      else:
      	  # 1. (n-1)개의 원반을 from막대에서 via막대로 이동
          moveDisc(discCnt-1, fromBar, viaBar, toBar)

          # 2. 큰 원반 1개를 from막대에서 to막대로 이동
          print(f'{discCnt}번 disc: {fromBar}막대에서 {toBar}막대로 이동!')

          # 3. (n-1)개의 원반을 via막대에서 to막대로 이동
          moveDisc(discCnt-1, viaBar, toBar, fromBar)

---